Locality-sensitive hashing of curves

A. Driemel, F. Silvestri

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)
98 Downloads (Pure)

Abstract

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).

Original languageEnglish
Title of host publication33rd International Symposium on Computational Geometry, SoCG 2017
EditorsB. Aronov, M.J. Katz
Place of PublicationDagstuhl
PublisherSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pages37:1-37:16
Number of pages16
Volume77
ISBN (Electronic)978-3-95977-038-5
DOIs
Publication statusPublished - 1 Jun 2017
Event33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia
Duration: 4 Jul 20177 Jul 2017
Conference number: 33
http://socg2017.smp.uq.edu.au/socg.html
http://socg2017.smp.uq.edu.au/index.html

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
Volume77

Conference

Conference33rd International Symposium on Computational Geometry (SoCG 2017)
Abbreviated titleSoCG 2017
CountryAustralia
CityBrisbane
Period4/07/177/07/17
OtherThe Computational Geometry Week (CG Week 2017) is the premier international forum for advances in computational geometry and its many applications. The next edition will take place in Brisbane, Australia, July 4-7, 2017.
CG week combines a number of events, most notably the 33rd International Symposium on Computational Geometry (SoCG 2017), the associated multimedia exposition, workshops, and the Young Researchers Forum.
Internet address

Keywords

  • Dynamic Time Warping
  • Fréchet distance
  • Locality-Sensitive hashing

Fingerprint Dive into the research topics of 'Locality-sensitive hashing of curves'. Together they form a unique fingerprint.

Cite this