@inproceedings{628d97d14c6e4e77b3c1d1d9eac51776,
title = "FRESH: Fr{\'e}chet Similarity with Hashing",
abstract = "This paper studies the r-range search problem for curves under the continuous Fr{\'e}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.",
keywords = "r-range search, continuous Fr{\'e}chet distance, polygonal curves, locality sensitive hashing, curve simplification",
author = "Matteo Ceccarello and Anne Driemel and Francesco Silvestri",
note = "Remove RP as author",
year = "2019",
doi = "10.1007/978-3-030-24766-9_19",
language = "English",
isbn = "978-3-030-24765-2",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
booktitle = "International Symposium on Algorithms and Data Structures (WADS)",
address = "Germany",
}