Locality-sensitive hashing of curves

A. Driemel, F. Silvestri

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

16 Citaten (Scopus)
104 Downloads (Pure)


We study data structures for storing a set of polygonal curves in IRd such that, given a query curve, we can efficiently retrieve similar curves from the set, where similarity is measured using the discrete Fréchet distance or the dynamic time warping distance. To this end we devise the first locality-sensitive hashing schemes for these distance measures. A major challenge is posed by the fact that these distance measures internally optimize the alignment between the curves. We give solutions for different types of alignments including constrained and unconstrained versions. For unconstrained alignments, we improve over a result by Indyk from 2002 [17] for short curves. Let n be the number of input curves and let m be the maximum complexity of a curve in the input. In the particular case where m ≤ α/4d log n, for some fixed α > 0, our solutions imply an approximate near-neighbor data structure for the discrete Fréchet distance that uses space in O(n1+αlog n) and achieves query time in O(nαlog2 n) and constant approximation factor. Furthermore, our solutions provide a trade-off between approximation quality and computational performance: for any parameter k ∈ [m], we can give a data structure that uses space in O(22kmk-1n log n + nm), answers queries in O(22kmklog n) time and achieves approximation factor in O(m/k).

Originele taal-2Engels
Titel33rd International Symposium on Computational Geometry, SoCG 2017
RedacteurenB. Aronov, M.J. Katz
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Aantal pagina's16
ISBN van elektronische versie978-3-95977-038-5
StatusGepubliceerd - 1 jun 2017
Evenement33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australië
Duur: 4 jul 20177 jul 2017
Congresnummer: 33

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)


Congres33rd International Symposium on Computational Geometry (SoCG 2017)
Verkorte titelSoCG 2017
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Locality-sensitive hashing of curves'. Samen vormen ze een unieke vingerafdruk.

Citeer dit