License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2017.37
URN: urn:nbn:de:0030-drops-72032
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7203/
Go to the corresponding LIPIcs Volume Portal

Driemel, Anne ; Silvestri, Francesco

Locality-Sensitive Hashing of Curves

pdf-format:
LIPIcs-SoCG-2017-37.pdf (0.6 MB)

Abstract

We study data structures for storing a set of polygonal curves in R^d 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 [SoCG 2002] 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 <= (a/(4d)) log n, for some fixed a>0, our solutions imply an approximate near-neighbor data structure for the discrete Fréchet distance that uses space in O(n^(1+a) log n) and achieves query time in O(n^a log^2 n) and constant approximation factor. Furthermore, our solutions provide a trade-off between approximation quality and computational performance: for any parameter k in [m], we can give a data structure that uses space in O(2^(2k) m^(k-1) n log n + nm), answers queries in O( 2^(2k) m^(k) log n) time and achieves approximation factor in O(m/k).

BibTeX - Entry

@InProceedings{driemel_et_al:LIPIcs:2017:7203,
  author =	{Anne Driemel and Francesco Silvestri},
  title =	{{Locality-Sensitive Hashing of Curves}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{37:1--37:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Boris Aronov and Matthew J. Katz},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7203},
  URN =		{urn:nbn:de:0030-drops-72032},
  doi =		{10.4230/LIPIcs.SoCG.2017.37},
  annote =	{Keywords: Locality-Sensitive Hashing, Frechet distance, Dynamic Time Warping}
}

Keywords: Locality-Sensitive Hashing, Frechet distance, Dynamic Time Warping
Collection: 33rd International Symposium on Computational Geometry (SoCG 2017)
Issue Date: 2017
Date of publication: 20.06.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI