ABSTRACT
Dynamic Time Warping (DTW) is a distance measure that compares two time series after optimally aligning them. DTW is being used for decades in thousands of academic and industrial projects despite the very expensive computational complexity, O(n2). These applications include data mining, image processing, signal processing, robotics and computer graphics among many others. In spite of all this research effort, there are many myths and misunderstanding about DTW in the literature, for example "it is too slow to be useful" or "the warping window size does not matter much." In this tutorial, we correct these misunderstandings and we summarize the research efforts in optimizing both the efficiency and effectiveness of both the basic DTW algorithm, and of the higher-level algorithms that exploit DTW such as similarity search, clustering and classification. We will discuss variants of DTW such as constrained DTW, multidimensional DTW and asynchronous DTW, and optimization techniques such as lower bounding, early abandoning, run-length encoding, bounded approximation and hardware optimization. We will discuss a multitude of application areas including physiological monitoring, social media mining, activity recognition and animal sound processing. The optimization techniques are generalizable to other domains on various data types and problems.
Supplemental Material
- T. Barto and T. Skopal, "Revisiting Techniques for Lower bounding the Dynamic Time Warping Distance," in Proceedings of the 5th International Conference on Similarity Search and Applications, 2012, pp. 192--208. Google ScholarDigital Library
- D. J. Berndt and J. Clifford, "Using Dynamic Time Warping to Find Patterns in Time Series," in KDD Workshop, 1994, pp. 359--370.Google Scholar
- Y. Chen, B. Hu, E. Keogh, and G. E. A. P.. Batista, "DTW-D: Time Series Semi-supervised Learning from a Single Example," in Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '13, 2013, p. 383. Google ScholarDigital Library
- S. Chu, E. Keogh, D. Hart, and M. Pazzani, "Iterative Deepening Dynamic Time Warping for Time Series," in Proceedings of the 2002 SIAM International Conference on Data Mining, 2002, pp. 195--212.Google Scholar
- P. Jangyodsuk, C. Conly, and V. 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, 2014, pp. 50:1--50:6. Google ScholarDigital Library
- E. Keogh, "Exact indexing of dynamic time warping," in Proceedings of the 28th international conference on Very Large Data Bases, 2002, pp. 406--417. Google ScholarDigital Library
- E. J. Keogh and M. J. Pazzani, "Scaling up dynamic time warping for data mining applications," in Proceedings of the sixth ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '00, 2000, pp. 285--289. Google ScholarDigital Library
- E. J. Keogh, L. Wei, X. Xi, S. Lee, and M. Vlachos, "LB_Keogh Supports Exact Indexing of Shapes under Rotation Invariance with Arbitrary Representations and Distance Measures," in Vldb, 2006, pp. 882--893. Google ScholarDigital Library
- S.-W. Kim, S. Park, and W. W. Chu, "An index-based approach for similarity search supporting time warping in large sequence databases," in Data Engineering, 2001. Proceedings. 17th International Conference on, 2001, pp. 607--614. Google ScholarDigital Library
- C. Myers, L. Rabiner, and A. Rosenberg, "Performance tradeoffs in dynamic time warping algorithms for isolated word recognition," IEEE Trans. Acoust., vol. 28, no. 6, pp. 623--635, Dec. 1980.Google ScholarCross Ref
- F. Petitjean, G. Forestier, G. I. Webb, A. E. Nicholson, Y. Chen, and E. Keogh, "Dynamic Time Warping Averaging of Time Series Allows Faster and More Accurate Classification," in 2014 IEEE International Conference on Data Mining, 2014, pp. 470--479. Google ScholarDigital Library
- L. R. Rabiner, A. E. Rosenberg, and S. E. Levinson, "Considerations in dynamic time warping algorithms for discrete word recognition," J. Acoust. Soc. Am., vol. 63, no. S1, pp. S79--S79, 1978.Google ScholarCross Ref
- T. Rakthanmanon, B. Campana, A. Mueen, G. Batista, B. Westover, Q. Zhu, J. Zakaria, and E. Keogh, "Searching and mining trillions of time series subsequences under dynamic time warping," in Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '12, 2012, p. 262. Google ScholarDigital Library
- T. M. Rath and R. Manmatha, "Word image matching using dynamic time warping," in Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, 2003, vol. 2, pp. II--521.Google Scholar
- H. Sakoe and S. Chiba, "Dynamic programming algorithm optimization for spoken word recognition," IEEE Trans. Acoust. Speech, Lang. Process., vol. 26, no. 1, pp. 43--50, 1978.Google ScholarCross Ref
- Y. Sakurai, C. Faloutsos, and M. Yamamuro, "Stream Monitoring under the Time Warping Distance," 2013 IEEE 29th Int. Conf. Data Eng., vol. 0, pp. 1046--1055, 2007.Google Scholar
- D. Sart, A. Mueen, W. Najjar, V. Niennattrakul, and E. Keogh, "Accelerating Dynamic Time Warping Subsequnce Search with GPUs and FPGAs. ICDM 2010," in Proceedings - IEEE International Conference on Data Mining, ICDM, 2010, pp. 1001--1006. Google ScholarDigital Library
- M. Toyoda, Y. Sakurai, and Y. Ishikawa, "Pattern Discovery in Data Streams Under the Time Warping Distance," VLDB J., vol. 22, no. 3, pp. 295--318, Jun. 2013. Google ScholarDigital Library
- N. Tselas and P. Papapetrou, "Benchmarking Dynamic Time Warping on Nearest Neighbor Classification of Electrocardiograms," in Proceedings of the 7th International Conference on PErvasive Technologies Related to Assistive Environments, 2014, pp. 4:1--4:4. Google ScholarDigital Library
- B.-K. Y. B.-K. Yi, H. V. Jagadish, and C. Faloutsos, "Efficient retrieval of similar time sequences under time warping," in Proceedings 14th International Conference on Data Engineering, 1998, pp. 201--208. Google ScholarDigital Library
- Q. Zhu, G. Batista, T. Rakthanmanon, and E. Keogh, "A Novel Approximation to Dynamic Time Warping allows Anytime Clustering of Massive Time Series Datasets," in Proceedings of the 2012 SIAM International Conference on Data Mining, 2012, pp. 999--1010.Google Scholar
- Y. Chen, G. Chen, K. Chen, and B. C. Ooi, "Efficient Processing of Warping Time Series Join of Motion Capture Data," in 2009 IEEE 25th International Conference on Data Engineering, 2009, pp. 1048--1059. Google ScholarDigital Library
- M. Shokoohi-Yekta, J. Wang, and E. Keogh, "On the Non-Trivial Generalization of Dynamic Time Warping to the Multi-Dimensional Case," in Proceedings of the 2015 SIAM International Conference on Data Mining, pp. 289--297.Google Scholar
- Keogh's Tutorials: http://www.cs.ucr.edu/~eamonn/tutorials.htmlGoogle Scholar
Index Terms
- Extracting Optimal Performance from Dynamic Time Warping
Recommendations
Asymptotic Dynamic Time Warping calculation with utilizing value repetition
Dynamic Time Warping (DTW) is a popular method for measuring the similarity of time series. It is widely used in various domains. A major drawback of DTW is that it has a high computational complexity. To address this problem, pruning techniques to ...
Flexible Dynamic Time Warping for Time Series Classification
Measuring the similarity or distance between two time series sequences is critical for the classification of a set of time series sequences. Given two time series sequences, X and Y , the dynamic time warping (DTW) algorithm can calculate the distance ...
Exact Dynamic Time Warping calculation for weak sparse time series
AbstractThe Dynamic Time Warping (DTW) technique is widely used in time series data mining. However, it should be pointed out that the calculation complexity of DTW is very high. In this paper, we propose an accurate and fast DTW calculation ...
Highlights- This paper addresses the accurate and fast DTW calculation algorithm on weak sparse time series.
Comments