Document Open Access Logo

A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length

Authors Yoshifumi Sakai, Shunsuke Inenaga

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.6.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Yoshifumi Sakai
  • Graduate School of Agricultural Science, Tohoku University, Sendai, Japan
Shunsuke Inenaga
  • Department of Informatics, Kyushu University, Fukuoka, Japan
  • PRESTO, Japan Science and Technology Agency, Kawaguchi, Japan

Funding

  • Inenaga, Shunsuke: The work of Shunsuke Inenaga was supported by JST PRESTO Grant Number JPMJPR1922.

Cite AsGet BibTex

Yoshifumi Sakai and Shunsuke Inenaga. A Reduction of the Dynamic Time Warping Distance to the Longest Increasing Subsequence Length. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ISAAC.2020.6

Abstract

The similarity between a pair of time series, i.e., sequences of indexed values in time order, is often estimated by the dynamic time warping (DTW) distance, instead of any in the well-studied family of measures including the longest common subsequence (LCS) length and the edit distance. Although it may seem as if the DTW and the LCS(-like) measures are essentially different, we reveal that the DTW distance can be represented by the longest increasing subsequence (LIS) length of a sequence of integers, which is the LCS length between the integer sequence and itself sorted. For a given pair of time series of n integers between zero and c, we propose an integer sequence that represents any substring-substring DTW distance as its band-substring LIS length. The length of the produced integer sequence is O(c⁴ n²) or O(c² n²) depending on the variant of the DTW distance used, both of which can be translated to O(n²) for constant cost functions. To demonstrate that techniques developed under the LCS(-like) measures are directly applicable to analysis of time series via our reduction of DTW to LIS, we present time-efficient algorithms for DTW-related problems utilizing the semi-local sequence comparison technique developed for LCS-related problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Pattern matching
Keywords
  • algorithms
  • dynamic time warping distance
  • longest increasing subsequence
  • semi-local sequence comparison

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 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 59-78. IEEE, 2015. Google Scholar
  2. Karl Bringmann and Marvin Künnemann. Quadratic conditional lower bounds for string problems and dynamic time warping. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pages 79-97. IEEE, 2015. Google Scholar
  3. Bernard Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM Journal on Computing, 17(3):427-462, 1988. Google Scholar
  4. Maxime Crochemore and Ely Porat. Fast computation of a longest increasing subsequence and application. Information and computation, 208(9):1054-1059, 2010. Google Scholar
  5. Marc Dupont and Pierre-François Marteau. Coarse-DTW for sparse time series alignment. In International Workshop on Advanced Analysis and Learning on Temporal Data, pages 157-172. Springer, 2015. Google Scholar
  6. Vincent Froese, Brijnesh Jain, Maciej Rymar, and Mathias Weller. Fast exact dynamic time warping on run-length encoded time series. arXiv preprint, 2020. URL: http://arxiv.org/abs/1903.03003.
  7. Omer Gold and Micha Sharir. Dynamic time warping and geometric edit distance: Breaking the quadratic barrier. ACM Transactions on Algorithms (TALG), 14(4):50:1-50:17, 2018. Google Scholar
  8. Daniel S. Hirschberg. A linear space algorithm for computing maximal common subsequences. Communications of the ACM, 18(6):341-343, 1975. Google Scholar
  9. Y Hwang and SB Gelfand. Binary sparse dynamic time warping. In Proceedings of the 15th International Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM’19), volume 2, pages 748-759, 2019. Google Scholar
  10. Youngha Hwang and Saul B Gelfand. Sparse dynamic time warping. In International Conference on Machine Learning and Data Mining in Pattern Recognition, pages 163-175. Springer, 2017. Google Scholar
  11. Zahedeh Izakian, Mohammad Saadi Mesgari, and Ajith Abraham. Automated clustering of trajectory data using a particle swarm optimization. Computers, Environment and Urban Systems, 55:55-65, 2016. Google Scholar
  12. Jyh-Shing Roger Jang and Hong-Ru Lee. Hierarchical filtering method for content-based music retrieval via acoustic input. In Proceedings of the ninth ACM international conference on Multimedia, pages 401-410, 2001. Google Scholar
  13. Pat Jangyodsuk, Christopher Conly, and Vassilis Athitsos. Sign language recognition using dynamic time warping and hand shape distance based on histogram of oriented gradient features. In Proceedings of the 7th International Conference on PErvasive Technologies Related to Assistive Environments, pages 50:1-50:6, 2014. Google Scholar
  14. Jingyu Jiang, Yuan Xing, Shuxin Wang, and Ke Liang. Evaluation of robotic surgery skills using dynamic time warping. Computer methods and programs in biomedicine, 152:71-83, 2017. Google Scholar
  15. Benjamin Johnen and Bernd Kuhlenkötter. A dynamic time warping algorithm for industrial robot motion analysis. In 2016 Annual Conference on Information Science and Systems (CISS), pages 18-23. IEEE, 2016. Google Scholar
  16. Eamonn Keogh and Chotirat Ratanamahatana. Exact indexing of dynamic time warping. Knowl. Inf. Syst., 7(3):358-386, 2005. Google Scholar
  17. William Kuszmaul. Dynamic time warping in strongly subquadratic time: Algorithms for the low-distance regime and approximate evaluation. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), pages 80:1-80:15, 2019. Google Scholar
  18. Lindasalwa Muda, Mumtaj Begam, and Irraivan Elamvazuthi. Voice recognition algorithms using mel frequency cepstral coefficient (MFCC) and dynamic time warping (DTW) techniques. arXiv preprint, 2010. URL: http://arxiv.org/abs/1003.4083.
  19. Abdullah Mueen, Nikan Chavoshi, Noor Abu-El-Rub, Hossein Hamooni, and Amanda Minnich. Awarp: fast warping distance for sparse time series. In 2016 IEEE 16th International Conference on Data Mining (ICDM), pages 350-359. IEEE, 2016. Google Scholar
  20. Meinard Müller. Dynamic time warping. Information retrieval for music and motion, pages 69-84, 2007. Google Scholar
  21. Toni M Rath and Raghavan Manmatha. Word image matching using dynamic time warping. In 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2003. Proceedings., volume 2, pages 521-527. IEEE, 2003. Google Scholar
  22. Yoshifumi Sakai. A fast algorithm for multiplying min-sum permutations. Discrete applied mathematics, 159(17):2175-2183, 2011. Google Scholar
  23. Yoshifumi Sakai. A substring-substring LCS data structure. Theoretical Computer Science, 753:16-34, 2019. Google Scholar
  24. Hiroaki Sakoe and Seibi Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE transactions on acoustics, speech, and signal processing, 26(1):43-49, 1978. Google Scholar
  25. Charles C. Tappert, Ching Y. Suen, and Toru Wakahara. The state of the art in online handwriting recognition. IEEE Transactions on pattern analysis and machine intelligence, 12(8):787-808, 1990. Google Scholar
  26. Alexander Tiskin. Semi-local string comparison: Algorithmic techniques and applications. Mathematics in Computer Science, 1(4):571-603, 2008. Google Scholar
  27. Alexander Tiskin. Fast distance multiplication of unit-Monge matrices. Algorithmica, 71(4):859-888, 2015. Google Scholar
  28. Neil Vaughan and Bogdan Gabrys. Comparing and combining time series trajectories using dynamic time warping. Procedia Computer Science, 96:465-474, 2016. Google Scholar
  29. 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 Imprint Privacy Contact