FRESH: Fréchet Similarity with Hashing

Matteo Ceccarello, Anne Driemel, Francesco Silvestri

    Research output: Conference Article in Proceeding or Book/Report chapterArticle in proceedingsResearchpeer-review

    Abstract

    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.
    Original languageEnglish
    Title of host publicationInternational Symposium on Algorithms and Data Structures (WADS)
    PublisherSpringer
    Publication date2019
    ISBN (Print)978-3-030-24765-2
    ISBN (Electronic)978-3-030-24766-9
    DOIs
    Publication statusPublished - 2019
    SeriesLecture Notes in Computer Science
    Volume11646
    ISSN0302-9743

    Keywords

    • r-range search
    • continuous Fréchet distance
    • polygonal curves
    • locality sensitive hashing
    • curve simplification

    Fingerprint

    Dive into the research topics of 'FRESH: Fréchet Similarity with Hashing'. Together they form a unique fingerprint.

    Cite this