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 localitysensitive 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 nearneighbor 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 tradeoff 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^(k1) 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 = {{LocalitySensitive Hashing of Curves}},
booktitle = {33rd International Symposium on Computational Geometry (SoCG 2017)},
pages = {37:137:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770385},
ISSN = {18688969},
year = {2017},
volume = {77},
editor = {Boris Aronov and Matthew J. Katz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7203},
URN = {urn:nbn:de:0030drops72032},
doi = {10.4230/LIPIcs.SoCG.2017.37},
annote = {Keywords: LocalitySensitive Hashing, Frechet distance, Dynamic Time Warping}
}
Keywords: 

LocalitySensitive Hashing, Frechet distance, Dynamic Time Warping 
Collection: 

33rd International Symposium on Computational Geometry (SoCG 2017) 
Issue Date: 

2017 
Date of publication: 

20.06.2017 