FRESH: Fréchet Similarity with Hashing

Matteo Ceccarello, Anne Driemel, Francesco Silvestri

Publikation: Konference artikel i Proceeding eller bog/rapport kapitelKonferencebidrag i proceedingsForskningpeer review

Abstrakt

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.
OriginalsprogEngelsk
TitelInternational Symposium on Algorithms and Data Structures (WADS)
ForlagSpringer
Publikationsdato2019
ISBN (Trykt)978-3-030-24765-2
ISBN (Elektronisk)978-3-030-24766-9
DOI
StatusUdgivet - 2019
NavnLecture Notes in Computer Science
Vol/bind11646
ISSN0302-9743

Fingeraftryk

Dyk ned i forskningsemnerne om 'FRESH: Fréchet Similarity with Hashing'. Sammen danner de et unikt fingeraftryk.

Citationsformater