TY - GEN
T1 - FRESH: Fréchet Similarity with Hashing
AU - Ceccarello, Matteo
AU - Driemel, Anne
AU - Silvestri, Francesco
N1 - Remove RP as author
PY - 2019
Y1 - 2019
N2 - This paper studies the r-range search problem for curves under the continuous Fréchet distance: given a dataset S of n polygonal curves and a threshold r>0 , construct a data structure that, for any query curve q, efficiently returns all entries in S with distance at most r from q. We propose FRESH, an approximate and randomized approach for r-range search, that leverages on a locality sensitive hashing scheme for detecting candidate near neighbors of the query curve, and on a subsequent pruning step based on a cascade of curve simplifications. We experimentally compare FRESH to exact and deterministic solutions, and we show that high performance can be reached by suitably relaxing precision and recall.
AB - This paper studies the r-range search problem for curves under the continuous Fréchet distance: given a dataset S of n polygonal curves and a threshold r>0 , construct a data structure that, for any query curve q, efficiently returns all entries in S with distance at most r from q. We propose FRESH, an approximate and randomized approach for r-range search, that leverages on a locality sensitive hashing scheme for detecting candidate near neighbors of the query curve, and on a subsequent pruning step based on a cascade of curve simplifications. We experimentally compare FRESH to exact and deterministic solutions, and we show that high performance can be reached by suitably relaxing precision and recall.
U2 - https://doi.org/10.1007/978-3-030-24766-9_19
DO - https://doi.org/10.1007/978-3-030-24766-9_19
M3 - Article in proceedings
SN - 978-3-030-24765-2
T3 - Lecture Notes in Computer Science
BT - International Symposium on Algorithms and Data Structures (WADS)
PB - Springer
ER -