Document Open Access Logo

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

Authors Omer Gold, Micha Sharir

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2017.25.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Omer Gold
Micha Sharir

Cite As Get BibTex

Omer Gold and Micha Sharir. Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ICALP.2017.25

Abstract

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space (X, dist). The DTW and GED measures are massively used in various fields of computer science and computational biology, consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in X = R^d are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case d = 1, which is perhaps one of the most used in practice.
	
In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of n points in R, by presenting deterministic algorithms that run in O( n^2 log log log n / log log n ) time. Our algorithms can be extended to work also for higher dimensional spaces R^d, for any constant d, when the underlying distance-metric dist is polyhedral (e.g., L_1, L_infty).

Subject Classification

Keywords
  • Dynamic Time Warping
  • Geometric Edit Distance
  • Time Series
  • Points Matching
  • Geometric Matching

Metrics

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

References

  1. A. Abboud, A. Backurs, and V. V. Williams. Tight hardness results for lcs and other sequence similarity measures. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 59-78, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.14.
  2. Amir Abboud, Thomas Dueholm Hansen, Virginia Vassilevska Williams, and Ryan Williams. Simulating branching programs with edit distance and friends: Or: A polylog shaved is a lower bound made. In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, pages 375-388, 2016. URL: http://dx.doi.org/10.1145/2897518.2897653.
  3. Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, and Micha Sharir. Computing the discrete Fréchet distance in subquadratic time. SIAM J. Comput., 43(2):429-449, 2014. URL: http://dx.doi.org/10.1137/130920526.
  4. Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating dynamic time warping and edit distance for a pair of point sequences. In Proceedings of the 32nd International Symposium on Computational Geometry, SoCG, pages 6:1-6:16, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.SoCG.2016.6.
  5. V. Arlazarov, E. Dinic, M. Kronrod, and I. Faradzev. On economical construction of the transitive closure of a directed graph. Dokl. Akad. Nauk., 194(11), 1970. Google Scholar
  6. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing, STOC, pages 51-58, 2015. URL: http://dx.doi.org/10.1145/2746539.2746612.
  7. Philip Bille and Martin Farach-Colton. Fast and compact regular expression matching. Theoretical Computer Science, 409(3):486-496, 2008. URL: http://dx.doi.org/10.1016/j.tcs.2008.08.042.
  8. Karl Bringmann. Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails. In Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pages 661-670, 2014. URL: http://dx.doi.org/10.1109/FOCS.2014.76.
  9. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proceedings of the 56th Annual IEEE Symposium on Foundations of Computer Science, FOCS, pages 79-97, 2015. URL: http://dx.doi.org/10.1109/FOCS.2015.15.
  10. Rainer E. Burkard, Bettina Klinz, and Rüdiger Rudolf. Perspectives of Monge properties in optimization. Discrete Applied Mathematics, 70(2):95-161, 1996. URL: http://dx.doi.org/10.1016/0166-218X(95)00103-X.
  11. E. G. Caiani, A. Porta, G. Baselli, M. Turiel, S. Muzzupappa, F. Pieruzzi, C. Crema, A. Malliani, and S. Cerutti. Warped-average template technique to track on a cycle-by-cycle basis the cardiac filling phases on left ventricular volume. In Computers in Cardiology, pages 73-76, 1998. URL: http://dx.doi.org/10.1109/CIC.1998.731723.
  12. T. M. Chan. All-pairs shortest paths with real weights in O(n³/log n) time. Algorithmica, 50(2):236-243, 2008. Google Scholar
  13. Alexander De Luca, Alina Hang, Frederik Brudy, Christian Lindner, and Heinrich Hussmann. Touch me once and I know it’s you!: Implicit authentication based on touch screen patterns. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, pages 987-996, 2012. URL: http://dx.doi.org/10.1145/2207676.2208544.
  14. Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, New York, 1998. Google Scholar
  15. 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, 2007. URL: http://dx.doi.org/10.1007/s10851-006-0647-0.
  16. M. L. Fredman. How good is the information theory bound in sorting? Theor. Comput. Sci, 1(4):355-361, 1976. Google Scholar
  17. M. L. Fredman. New bounds on the complexity of the shortest path problem. SIAM J. Comput., 5(1):83-89, 1976. Google Scholar
  18. Omer Gold and Micha Sharir. Improved bounds for 3SUM, k-SUM, and linear degeneracy. CoRR, abs/1512.05279, 2015. Google Scholar
  19. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. CoRR, abs/1607.05994, 2016. URL: http://arxiv.org/abs/1607.05994.
  20. Szymon Grabowski. New tabulation and sparse dynamic programming based techniques for sequence similarity problems. Discrete Applied Mathematics, 212:96-103, 2016. Stringology Algorithms. URL: http://dx.doi.org/10.1016/j.dam.2015.10.040.
  21. A. Grønlund and S. Pettie. Threesomes, degenerates, and love triangles. In Proceedings 55th Annual Symposium on Foundations of Computer Science (FOCS), pages 621-630, 2014. Google Scholar
  22. Russel Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. URL: http://dx.doi.org/10.1006/jcss.2000.1727.
  23. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which problems have strongly exponential complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. URL: http://dx.doi.org/10.1006/jcss.2001.1774.
  24. Haim Kaplan, Shay Mozes, Yahav Nussbaum, and Micha Sharir. Submatrix maximum queries in Monge matrices and Monge partial matrices, and their applications. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 338-355, 2012. Google Scholar
  25. Eamonn Keogh and Ann Chotirat Ratanamahatana. Exact indexing of dynamic time warping. Knowledge and Information Systems, 7(3):358-386, 2005. URL: http://dx.doi.org/10.1007/s10115-004-0154-9.
  26. Eamonn J. Keogh and Michael J. Pazzani. Scaling up Dynamic Time Warping to Massive Datasets, pages 1-11. Springer Berlin-Heidelberg, 1999. URL: http://dx.doi.org/10.1007/978-3-540-48247-5_1.
  27. Eamonn J. Keogh and Michael J. Pazzani. Scaling up dynamic time warping for datamining applications. In Proceedings of the 6th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 285-289, 2000. URL: http://dx.doi.org/10.1145/347090.347153.
  28. Theo Gasser Kongming Wang. Alignment of curves by dynamic time warping. Annals of Statistics, 25(3):1251-1276, 1997. Google Scholar
  29. William J. Masek and Michael S. Paterson. A faster algorithm computing string edit distances. Journal of Computer and System Sciences, 20(1):18-31, 1980. URL: http://dx.doi.org/10.1016/0022-0000(80)90002-1.
  30. Meinard Müller. Information Retrieval for Music and Motion, pages 69-84. Springer Berlin-Heidelberg, 2007. URL: http://dx.doi.org/10.1007/978-3-540-74048-3_4.
  31. F. P. Preparata and M. I. Shamos. Computational Geometry. Springer, New York, NY, 1985. Google Scholar
  32. Chotirat A. Ratanamahatana and Eamonn Keogh. Three myths about dynamic time warping data mining. In Proceedings of the 2005 SIAM International Conference on Data Mining, pages 506-510, 2005. URL: http://dx.doi.org/10.1137/1.9781611972757.50.
  33. T. K. Vintsyuk. Speech discrimination by dynamic programming. Cybernetics, 4(1):52-57, 1968. URL: http://dx.doi.org/10.1007/BF01074755.
  34. Xiaoyue Wang, Abdullah Mueen, Hui Ding, Goce Trajcevski, Peter Scheuermann, and Eamonn Keogh. Experimental comparison of representation methods and distance measures for time series data. Data Mining and Knowledge Discovery, 26(2):275-309, 2013. URL: http://dx.doi.org/10.1007/s10618-012-0250-5.
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 About DROPS Imprint Privacy Contact