FRESH Frechet Similarity With Hashing

Ceccarello Matteo, Driemel Anne, Silvestri Francesco. Proc. of Algorithms and Data Structures Symposium 2018

[Paper]    
Independent

This paper studies the $r$-range search problem for curves under the continuous Fr'echet 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.

Similar Work

• Locality-sensitive Hashing Of Curves
• Hashing Geographical Point Data Using The Space-filling H-curve
• Elliptic Curve Multiset Hash
• A Linear-time Approximation Of The Earth Movers Distance