## Abstract

We study data structures for storing a set of polygonal curves in IR^{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 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(n^{1+α}log n) and achieves query time in O(n^{α}log^{2} 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(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).

Original language | English |
---|---|

Title of host publication | 33rd International Symposium on Computational Geometry, SoCG 2017 |

Editors | B. Aronov, M.J. Katz |

Place of Publication | Dagstuhl |

Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |

Pages | 37:1-37:16 |

Number of pages | 16 |

Volume | 77 |

ISBN (Electronic) | 978-3-95977-038-5 |

DOIs | |

Publication status | Published - 1 Jun 2017 |

Event | 33rd International Symposium on Computational Geometry (SoCG 2017) - University of Queensland, Brisbane, Australia Duration: 4 Jul 2017 → 7 Jul 2017 Conference number: 33 http://socg2017.smp.uq.edu.au/socg.html http://socg2017.smp.uq.edu.au/index.html |

### Publication series

Name | Leibniz International Proceedings in Informatics (LIPIcs) |
---|---|

Volume | 77 |

### Conference

Conference | 33rd International Symposium on Computational Geometry (SoCG 2017) |
---|---|

Abbreviated title | SoCG 2017 |

Country | Australia |

City | Brisbane |

Period | 4/07/17 → 7/07/17 |

Other | The 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