Document Open Access Logo

Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

Authors Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, Rex Ying

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2016.6.pdf
  • Filesize: 0.67 MB
  • 16 pages

Document Identifiers

Author Details

Pankaj K. Agarwal
Kyle Fox
Jiangwei Pan
Rex Ying

Cite As Get BibTex

Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences. In 32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.SoCG.2016.6

Abstract

We present the first subquadratic algorithms for computing similarity between a pair of point sequences in R^d, for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + eps)-approximations of DTW and ED in near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1.

The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimum-weight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimum-weight paths through these rectangles.

Subject Classification

Keywords
  • Dynamic time warping
  • Edit distance
  • Near-linear-time algorithm
  • Dynamic programming
  • Well-separated pair decomposition

Metrics

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

References

  1. Amir Abboud, Arturs Backurs, and Virginia Vassilevska Williams. Tight hardness results for LCS and other sequence similarity measures. In Proc. 56th Annu. IEEE Sympos. on Found. Comp. Sci., pages 59-78, 2015. Google Scholar
  2. Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Proc. 41st Int. Colloq. on Auto., Lang., and Program., pages 39-51, 2014. Google Scholar
  3. Helmut Alt, Christian Knauer, and Carola Wenk. Comparison of distance measures for planar curves. Algorithmica, 38(1):45-58, 2004. Google Scholar
  4. Alexandr Andoni, Robert Krauthgamer, and Krzysztof Onak. Polylogarithmic approximation for edit distance and the asymmetric query complexity. In Proc. 51st IEEE Sympos. on Found. Comp. Sci., pages 377-386, 2010. Google Scholar
  5. Boris Aronov, Sariel Har-Peled, Christian Knauer, Yusu Wang, and Carola Wenk. Fréchet distance for curves, revisited. In Proc. 14th Annu. Euro. Sympos. Algo., pages 52-63, 2006. Google Scholar
  6. Arturs Backurs and Piotr Indyk. Edit distance cannot be computed in strongly subquadratic time (unless SETH is false). In Proc. 47th Annu. ACM Sympos. Theory of Comput., pages 51-58, 2015. Google Scholar
  7. Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails. In Proc. 55th. Annu. IEEE Sympos. on Found. of Comp. Sci., pages 661-670, 2014. Google Scholar
  8. Karl Bringmann and Marvin Künnemann. Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds. In Proc. 26th Annu. Int. Sympos. Algo. Comp., pages 517-528, 2015. Google Scholar
  9. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In Proc. 56th Annu. IEEE Sympos. on Found. of Comp. Sci., pages 79-97, 2015. Google Scholar
  10. Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete Fréchet distance. J. Comput. Geom., 7(2):46-76, 2016. Google Scholar
  11. Thomas Brox and Jitendra Malik. Object segmentation by long term analysis of point trajectories. In Proc. 11th Annu. Euro. Conf. Comp. Vis., pages 282-295, 2010. Google Scholar
  12. Paul B. Callahan and S. Rao Kosaraju. A decomposition of multidimensional point sets with applications to k-nearest-neighbors and n-body potential fields. J. ACM, 42(1):67-90, 1995. Google Scholar
  13. Cartesian tree. URL: https://en.wikipedia.org/wiki/Cartesian_tree.
  14. 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 Proc. SIGCHI Conf. Human Factors in Comp. Sys., pages 987-996, 2012. Google Scholar
  15. Anne Driemel, Sariel Har-Peled, and Carola Wenk. Approximating the Fréchet distance for realistic curves in near linear time. Discrete Comp. Geom., 48(1):94-127, 2012. Google Scholar
  16. Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison. Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Camridge University Press, New York, 1998. Google Scholar
  17. Johannes Fischer and Volker Heun. Theoretical and practical improvements on the RMQ-problem, with applications to LCA and LCE. In Proc. 17th Annu. Sympos. Combin. Pattern Match., pages 36-48, 2006. Google Scholar
  18. T. Gasser and K. Wang. Alignment of curves by dynamic time warping. Annals of Statistics, 25(3):1251-1276, 1997. Google Scholar
  19. M. C. Gonzalez, C. A. Hidalgo, and A.-L. Barabasi. Understanding individual human mobility patterns. Nature, 453(7196):779-782, 2008. Google Scholar
  20. Sariel Har-Peled. Geometric Approximation Algorithms. American Mathematical Society Providence, 2011. Google Scholar
  21. Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-SAT. J. Comp. Sys. Sci., 62(2):367-375, 201. Google Scholar
  22. Jon Kleinberg and Eva Tardos. Algorithm Design. Addison-Wesley Longman Publishing Co., Inc., 2005. Google Scholar
  23. Rachel Kolodny, Patrice Koehl, and Michael Levitt. Comprehensive evaluation of protein structure alignment methods: Scoring by geometric measures. J. Mol. Bio., 346(4):1173-1188, 2005. Google Scholar
  24. J.-G. Lee, J. Han, and K.-Y. Whang. Trajectory clustering: a partition-and-group framework. In Proc. ACM SIGMOD Int. Conf. Manag. Data, pages 593-604, 2007. Google Scholar
  25. Meinard Müller. Information Retrieval for Music and Motion. Springer-Verlag Berlin Heidelberg, 2007. Google Scholar
  26. Mario E. Munich and Pietro Perona. Continuous dynamic time warping for translation-invariant curve alignment with applications to signature verification. In Proc. 7th Annu. Int. Conf. Comp. Vis., pages 108-115, 1999. Google Scholar
  27. L.R. Rabiner and B.H. Juang. Fundamentals of Speech Recognition. PTR Prentice Hall, 1993. Google Scholar
  28. Range minimum queries: Part two. URL: http://web.stanford.edu/class/archive/cs/cs166/cs166.1146/lectures/01/Slides01.pdf.
  29. Time series matching with dynamic time warping. URL: https://systematicinvestor.wordpress.com/2012/01/20/time-series-matching-with-dynamic-time-warping/.
  30. 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. Google Scholar
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