Gå til søgefeltetSpring over til navigationSpring til hovedindhold

FRESH: Fréchet Similarity with Hashing

  • Matteo Ceccarello
    ,
  • Anne Driemel
    ,
  • Francesco Silvestri
  • University of Bonn
Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Konferencebidrag i proceedings
Forskning
Peer-review

Open Access

Resume

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.

Publikation information

Produktionstype

Publikation:
Konference artikel i Proceeding eller bog/rapport kapitel
Konferencebidrag i proceedings
Forskning
Peer-review

Originalsprog

Engelsk

Publikationsmilepæle

  • Udgivet - 2019

Publikationsstatus

Udgivet - 2019

Forlag

Springer, USA, Tyskland

Bogserie

  • Bogserienavn: Lecture Notes in Computer Science
    Bind: 11646
    ISSN: 0302-9743
978-3-030-24765-2

ISBN (Elektronisk)

978-3-030-24766-9

Publikations IDer

  • Scopus: 85070577654

Titel på værtspublikation

International Symposium on Algorithms and Data Structures (WADS)

Metrikker

PlumX, åbner i en ny fane

Hentninger
16
Antal citationer
16