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.2018.37
URN: urn:nbn:de:0030-drops-87504
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8750/
Go to the corresponding LIPIcs Volume Portal

Emiris, Ioannis Z. ; Psarros, Ioannis

Products of Euclidean Metrics and Applications to Proximity Questions among Curves

pdf-format:
LIPIcs-SoCG-2018-37.pdf (0.5 MB)

Abstract

The problem of Approximate Nearest Neighbor (ANN) search is fundamental in computer science and has benefited from significant progress in the past couple of decades. However, most work has been devoted to pointsets whereas complex shapes have not been sufficiently treated. Here, we focus on distance functions between discretized curves in Euclidean space: they appear in a wide range of applications, from road segments and molecular backbones to time-series in general dimension. For l_p-products of Euclidean metrics, for any p >= 1, we design simple and efficient data structures for ANN, based on randomized projections, which are of independent interest. They serve to solve proximity problems under a notion of distance between discretized curves, which generalizes both discrete Fréchet and Dynamic Time Warping distances. These are the most popular and practical approaches to comparing such curves. We offer the first data structures and query algorithms for ANN with arbitrarily good approximation factor, at the expense of increasing space usage and preprocessing time over existing methods. Query time complexity is comparable or significantly improved by our algorithms; our approach is especially efficient when the length of the curves is bounded.

BibTeX - Entry

@InProceedings{emiris_et_al:LIPIcs:2018:8750,
  author =	{Ioannis Z. Emiris and Ioannis Psarros},
  title =	{{Products of Euclidean Metrics and Applications to Proximity Questions among Curves}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{37:1--37:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Bettina Speckmann and Csaba D. T{\'o}th},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8750},
  URN =		{urn:nbn:de:0030-drops-87504},
  doi =		{10.4230/LIPIcs.SoCG.2018.37},
  annote =	{Keywords: Approximate nearest neighbor, polygonal curves, Fr{\'e}chet distance, dynamic time warping}
}

Keywords: Approximate nearest neighbor, polygonal curves, Fréchet distance, dynamic time warping
Collection: 34th International Symposium on Computational Geometry (SoCG 2018)
Issue Date: 2018
Date of publication: 08.06.2018

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