Document Open Access Logo

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves

Authors Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx , André Nusser

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.20.pdf
  • Filesize: 0.9 MB
  • 17 pages

Document Identifiers

Author Details

Karl Bringmann
  • Universität des Saarlandes, Saarbrücken, Germany
  • Max Planck Institute for Informatics, Saarland Informatics Campus, Saarbrücken, Germany
Sándor Kisfaludi‑Bak
  • Aalto University, Espoo, Finland
Marvin Künnemann
  • Institute for Theoretical Studies, ETH Zürich, Switzerland
Dániel Marx
  • CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
André Nusser
  • BARC, University of Copenhagen, Denmark

Funding

  • Bringmann, Karl: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979).
  • Kisfaludi‑Bak, Sándor: Part of this research was conducted while the author was at the Max Planck Institute for Informatics, and part of it while he was at the Institute for Theoretical Studies, ETH Zürich.
  • Künnemann, Marvin: Research supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by the ETH Zürich Foundation.
  • Marx, Dániel: Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH.
  • Nusser, André: Part of this research was conducted while the author was at Saarbrücken Graduate School of Computer Science and Max Planck Institute for Informatics. The author is supported by the VILLUM Foundation grant 16582.

Acknowledgements

We thank Christian Wulff-Nilsen for making us aware of an improved offline dynamic shortest paths data structure.

Cite AsGet BibTex

Karl Bringmann, Sándor Kisfaludi‑Bak, Marvin Künnemann, Dániel Marx, and André Nusser. Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 20:1-20:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.20

Abstract

The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlier-insensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location? There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L₁ norm in ℝ^d, we provide an 𝒪(n^{2(d+1)})-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problem-specific insight leads to a (1+ε)-approximation in time 𝒪(n³/ε²). We then show how to obtain a subcubic 𝒪̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the well-known quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using space-filling curves in a way that incurs only few updates to the data structure. We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
Keywords
  • Dynamic Time Warping
  • Sequence Similarity Measures

Metrics

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

Related Versions

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 59-78. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.14.
  2. Amir Abboud and Søren Dahlgaard. Popular conjectures as a barrier for dynamic planar graph algorithms. In Irit Dinur, editor, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey, USA, pages 477-486. IEEE Computer Society, 2016. URL: https://doi.org/10.1109/FOCS.2016.58.
  3. Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating dynamic time warping and edit distance for a pair of point sequences. In Sándor P. Fekete and Anna Lubiw, editors, 32nd International Symposium on Computational Geometry, SoCG 2016, June 14-18, 2016, Boston, MA, USA, volume 51 of LIPIcs, pages 6:1-6:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.SoCG.2016.6.
  4. Helmut Alt and Michael Godau. Computing the Fréchet distance between two polygonal curves. Internat. J. Comput. Geom. Appl., 5(1-2):78-99, 1995. Google Scholar
  5. Helmut Alt, Christian Knauer, and Carola Wenk. Matching polygonal curves with respect to the Fréchet distance. In Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science (STACS'01), pages 63-74, 2001. Google Scholar
  6. Chandrajit L. Bajaj. The algebraic degree of geometric optimization problems. Discret. Comput. Geom., 3:177-191, 1988. URL: https://doi.org/10.1007/BF02187906.
  7. Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. A faster algorithm for the discrete Fréchet distance under translation. ArXiv preprint, 2015. URL: http://arxiv.org/abs/1501.03724.
  8. Sotiris Brakatsoulas, Dieter Pfoser, Randall Salas, and Carola Wenk. On map-matching vehicle tracking data. In Proc. 31st International Conf. Very Large Data Bases (VLDB'05), pages 853-864, 2005. Google Scholar
  9. Milutin Brankovic, Kevin Buchin, Koen Klaren, André Nusser, Aleksandr Popov, and Sampson Wong. (k, l)-medians clustering of trajectories using continuous dynamic time warping. In Chang-Tien Lu, Fusheng Wang, Goce Trajcevski, Yan Huang, Shawn D. Newsam, and Li Xiong, editors, SIGSPATIAL '20: 28th International Conference on Advances in Geographic Information Systems, Seattle, WA, USA, November 3-6, 2020, pages 99-110. ACM, 2020. URL: https://doi.org/10.1145/3397536.3422245.
  10. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th Ann. IEEE Symposium on Foundations of Computer Science (FOCS'14), pages 661-670, 2014. Google Scholar
  11. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 79-97. IEEE Computer Society, 2015. URL: https://doi.org/10.1109/FOCS.2015.15.
  12. Karl Bringmann, Marvin Künnemann, and André Nusser. When Lipschitz walks your dog: Algorithm engineering of the discrete Fréchet distance under translation. In Fabrizio Grandoni, Grzegorz Herman, and Peter Sanders, editors, 28th Annual European Symposium on Algorithms, ESA 2020, September 7-9, 2020, Pisa, Italy (Virtual Conference), volume 173 of LIPIcs, pages 25:1-25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. URL: https://doi.org/10.4230/LIPIcs.ESA.2020.25.
  13. Karl Bringmann, Marvin Künnemann, and André Nusser. Discrete Fréchet distance under translation: Conditional hardness and an improved algorithm. ACM Trans. Algorithms, 17(3):25:1-25:42, 2021. URL: https://doi.org/10.1145/3460656.
  14. Maike Buchin. On the computability of the Fréchet distance between triangulated surfaces. PhD thesis, Freie Universität Berlin, 2007. PhD Thesis. Google Scholar
  15. Michael B. Cohen, Yin Tat Lee, Gary L. Miller, Jakub Pachocki, and Aaron Sidford. Geometric median in nearly linear time. In Daniel Wichs and Yishay Mansour, editors, Proc. 48th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2016), pages 9-21. ACM, 2016. URL: https://doi.org/10.1145/2897518.2897647.
  16. Debarati Das, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen. A near-optimal offline algorithm for dynamic all-pairs shortest paths in planar digraphs. In Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3482-3495, 2022. URL: https://doi.org/10.1137/1.9781611977073.138.
  17. Mark de Berg and Atlas F. Cook. Go with the flow: The direction-based Fréchet distance of polygonal curves. In Alberto Marchetti-Spaccamela and Michael Segal, editors, Theory and Practice of Algorithms in (Computer) Systems - First International ICST Conference, TAPAS 2011, Rome, Italy, April 18-20, 2011. Proceedings, volume 6595 of Lecture Notes in Computer Science, pages 81-91. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-19754-3_10.
  18. Alon Efrat, Quanfu Fan, and Suresh Venkatasubramanian. Curve Matching, Time Warping, and Light Fields: New Algorithms for Computing Similarity between Curves. Journal of Mathematical Imaging and Vision, 27(3):203-216, April 2007. URL: https://doi.org/10.1007/s10851-006-0647-0.
  19. Alon Efrat, Piotr Indyk, and Suresh Venkatasubramanian. Pattern matching for sets of segments. In Proc. 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'01), pages 295-304, 2001. Google Scholar
  20. Thomas Eiter and Heikki Mannila. Computing discrete Fréchet distance. Technical Report CD-TR 94/64, Christian Doppler Laboratory for Expert Systems, TU Vienna, Austria, 1994. Google Scholar
  21. Jittat Fakcharoenphol and Satish Rao. Planar graphs, negative weight edges, shortest paths, and near linear time. J. Comput. Syst. Sci., 72(5):868-889, 2006. URL: https://doi.org/10.1016/j.jcss.2005.05.007.
  22. Pawel Gawrychowski and Adam Karczmarz. Improved bounds for shortest paths in dense distance graphs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 61:1-61:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.61.
  23. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. ACM Trans. Algorithms, 14(4):50:1-50:17, 2018. URL: https://doi.org/10.1145/3230734.
  24. Joachim Gudmundsson, André van Renssen, Zeinab Saeidi, and Sampson Wong. Translation invariant Fréchet distance queries. Algorithmica, 83(11):3514-3533, 2021. URL: https://doi.org/10.1007/s00453-021-00865-0.
  25. Sariel Har-Peled. Geometric approximation algorithms, chapter Fréchet distance: How to walk your dog, pages 383-412. American Mathematical Society, 2017. Online chapter. Google Scholar
  26. Minghui Jiang, Ying Xu, and Binhai Zhu. Protein structure-structure alignment with discrete Fréchet distance. J. Bioinformatics and Computational Biology, 6(01):51-64, 2008. Google Scholar
  27. Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in monge matrices and partial monge matrices, and their applications. ACM Trans. Algorithms, 13(2):26:1-26:42, 2017. URL: https://doi.org/10.1145/3039873.
  28. Philip N. Klein. Multiple-source shortest paths in planar graphs. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005, pages 146-155. SIAM, 2005. URL: http://dl.acm.org/citation.cfm?id=1070432.1070454.
  29. Marvin Künnemann and André Nusser. Polygon placement revisited: (Degree of Freedom + 1)-SUM hardness and an improvement via offline dynamic rectangle union. In Proc. 33rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'22), 2022. To appear. Google Scholar
  30. William Kuszmaul. Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 80:1-80:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.80.
  31. Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the integral Fréchet distance. Comput. Geom., 70-71:13-30, 2018. URL: https://doi.org/10.1016/j.comgeo.2018.01.001.
  32. Axel Mosig and Michael Clausen. Approximately matching polygonal curves with respect to the Fréchet distance. Computational Geometry: Theory and Applications, 30(2):113-127, 2005. Google Scholar
  33. Mario E. Munich and Pietro Perona. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proceedings of the International Conference on Computer Vision, Kerkyra, Corfu, Greece, September 20-25, 1999, pages 108-115. IEEE Computer Society, 1999. URL: https://doi.org/10.1109/ICCV.1999.791205.
  34. Mark H. Overmars and Chee-Keng Yap. New upper bounds in klee’s measure problem. SIAM J. Comput., 20(6):1034-1045, 1991. URL: https://doi.org/10.1137/0220065.
  35. Michail Vlachos, George Kollios, and Dimitrios Gunopulos. Elastic Translation Invariant Matching of Trajectories. Machine Learning, 58(2):301-334, February 2005. URL: https://doi.org/10.1007/s10994-005-5830-9.
  36. Carola Wenk. Shape matching in higher dimensions. PhD thesis, Freie Universität Berlin, 2003. PhD Thesis. Google Scholar
  37. Carola Wenk, Randall Salas, and Dieter Pfoser. Addressing the need for map-matching speed: Localizing globalb curve-matching algorithms. In 18th International Conference on Scientific and Statistical Database Management, SSDBM 2006, 3-5 July 2006, Vienna, Austria, Proceedings, pages 379-388. IEEE Computer Society, 2006. URL: https://doi.org/10.1109/SSDBM.2006.11.
  38. Rex Ying, Jiangwei Pan, Kyle Fox, and Pankaj K. Agarwal. A simple efficient approximation algorithm for dynamic time warping. In Siva Ravada, Mohammed Eunus Ali, Shawn D. Newsam, Matthias Renz, and Goce Trajcevski, editors, Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS 2016, Burlingame, California, USA, October 31 - November 3, 2016, pages 21:1-21:10. ACM, 2016. URL: https://doi.org/10.1145/2996913.2996954.
  39. Yu Qiao and M. Yasuhara. Affine Invariant Dynamic Time Warping and its Application to Online Rotated Handwriting Recognition. In 18th International Conference on Pattern Recognition (ICPR'06), volume 2, pages 905-908, August 2006. ISSN: 1051-4651. URL: https://doi.org/10.1109/ICPR.2006.228.
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact