Products of Euclidean Metrics and Applications to Proximity Questions among Curves

Authors Ioannis Z. Emiris, Ioannis Psarros



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2018.37.pdf
  • Filesize: 489 kB
  • 13 pages

Document Identifiers

Author Details

Ioannis Z. Emiris
Ioannis Psarros

Cite AsGet BibTex

Ioannis Z. Emiris and Ioannis Psarros. Products of Euclidean Metrics and Applications to Proximity Questions among Curves. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 37:1-37:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.SoCG.2018.37

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.
Keywords
  • Approximate nearest neighbor
  • polygonal curves
  • Fréchet distance
  • dynamic time warping

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. E. Anagnostopoulos, I. Z. Emiris, and I. Psarros. Low-quality dimension reduction and high-dimensional approximate nearest neighbor. In Proc. 31st Intern. Symp. on Computational Geometry (SoCG), pages 436-450, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.SOCG.2015.436.
  2. E. Anagnostopoulos, I. Z. Emiris, and I. Psarros. Randomized embeddings with slack, and high-dimensional approximate nearest neighbor. In ACM Transactions on Algorithm, 2018, To appear. Google Scholar
  3. A. Andoni. NN search: the old, the new, and the impossible. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA, USA, 2009. URL: http://hdl.handle.net/1721.1/55090.
  4. A. Andoni, T. Laarhoven, I. Razenshteyn, and E. Waingarten. Optimal hashing-based time-space trade-offs for approximate near neighbors. In Proc. Symp. Discrete Algorithms (SODA), 2017. Also as arxiv.org/abs/1608.03580. Google Scholar
  5. S. Arya, T. Malamatos, and D. M. Mount. Space-time tradeoffs for approximate nearest neighbor searching. J. ACM, 57(1):1:1-1:54, 2009. URL: http://dx.doi.org/10.1145/1613676.1613677.
  6. Y. Bartal and L. -A. Gottlieb. Dimension reduction techniques for l_p (1lesspless2), with applications. In 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, pages 16:1-16:15, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.16.
  7. A. Driemel and F. Silvestri. Locality-sensitive hashing of curves. In Proc. 33rd Intern. Symposium on Computational Geometry, pages 37:1-37:16, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2017.37.
  8. S. Har-Peled, P. Indyk, and R. Motwani. Approximate nearest neighbor: Towards removing the curse of dimensionality. Theory of Computing, 8(1):321-350, 2012. URL: http://dx.doi.org/10.4086/toc.2012.v008a014.
  9. S. Har-Peled and M. Mendel. Fast construction of nets in low dimensional metrics, and their applications. In Proc. 21st Annual Symp. Computational Geometry, SCG'05, pages 150-158, 2005. URL: http://dx.doi.org/10.1145/1064092.1064117.
  10. P. Indyk. Approximate nearest neighbor algorithms for frechet distance via product metrics. In Proc. 18th Annual Symp. on Computational Geometry, SCG '02, pages 102-106, New York, NY, USA, 2002. ACM. URL: http://dx.doi.org/10.1145/513400.513414.
  11. J. Matoušek. On variants of the Johnson-Lindenstrauss lemma. Random Struct. Algorithms, 33(2):142-156, 2008. URL: http://dx.doi.org/10.1002/rsa.v33:2.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail