Abstract
The dynamic time warping (DTW) distance has been used as a popular measure to compare similarities of numeric time series because it provides robust matching that recognizes warps in time, different sampling rate, etc. Although DTW computation can be optimized by dynamic programming, it is still expensive, so there have been many attempts proposed to speedup DTW-based similarity search by distance lowerbounding. Some approaches assume a constrained variant of DTW (i.e., fixed dimensions, warping window constraint, ground distance), while others do not. In this paper, we comprehensively revisit the problem of DTW lowerbounding, define a general form of DTW that fits all the existing variants and goes even beyond. For the constrained variants of general DTW we propose a lowerbound construction generalizing the LB_Keogh that for particular ground distances offers speedup by up to two orders of magnitude. Furthermore, we apply metric and ptolemaic lowerbounding on unconstrained variants of general DTW that beats the few existing competitors up to two orders of magnitude.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Assent, I., Wichterich, M., Krieger, R., Kremer, H., Seidl, T.: Anticipatory dtw for efficient similarity search in time series databases. Proc. VLDB Endow. 2, 826–837 (2009)
Berndt, D.J., Clifford, J.: Using Dynamic Time Warping to Find Patterns in Time Series. In: KDD Workshop, pp. 359–370 (1994)
Camerra, A., Palpanas, T., Shieh, J., Keogh, E.: iSAX 2.0:indexing and mining one billion time series. In: IEEE International Conf. on Data Mining, pp. 58–67 (2010)
Chávez, E., Navarro, G., Baeza-Yates, R., Marroquín, J.L.: Searching in metric spaces. ACM Computing Surveys 33(3), 273–321 (2001)
Hetland, M.L.: Ptolemaic indexing. arXiv:0911.4384 [cs.DS] (2009)
Junkui, L., Yuanzhen, W.: Early abandon to accelerate exact dynamic time warping. Int. Arab. J. Inf. Technol. 6(2), 144–152 (2009)
Keogh, E.: Exact indexing of dynamic time warping. In: Proceedings of the 28th International Conference on Very Large Data Bases, pp. 406–417 (2002)
Keogh, E., Ratanamahatana, C.A.: Exact indexing of dynamic time warping. Knowledge and Information Systems 7, 358–386 (2005), doi:10.1007/s10115-004-0154-9
Keogh, E., Xi, X., Wei, L., Ratanamahatana, C.: The UCR Time Series Classification/Clustering Homepage (2006)
Kim, S.-W., Park, S., Chu, W.W.: An index-based approach for similarity search supporting time warping in large sequence databases. In: Proceedings of the 17th International Conference on Data Engineering, pp. 607–614. IEEE Computer Society, Washington, DC (2001)
Lokoč, J., Hetland, M.L., Skopal, T., Beecks, C.: Ptolemaic indexing of the signature quadratic form distance. In: Proceedings of the Fourth International Conference on Similarity Search and Applications, pp. 9–16. ACM (2011)
Mico, M.L., Oncina, J., Vidal, E.: A new version of the nearest-neighbour approximating and eliminating search algorithm (aesa) with linear preprocessing time and memory requirements. Pattern Recogn. Lett. 15(1), 9–17 (1994)
Rabiner, L., Juang, B.-H.: Fundamentals of speech recognition. Prentice-Hall, Inc., Upper Saddle River (1993)
Sakoe, H.: Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. on Acoustics, Speech, and Signal Processing 26, 43–49 (1978)
Shieh, J., Keogh, E.J.: iSAX: disk-aware mining and indexing of massive time series datasets. Data Min. Knowl. Discov. 19(1), 24–57 (2009)
Skopal, T.: On Fast Non-metric Similarity Search by Metric Access Methods. In: Ioannidis, Y., Scholl, M.H., Schmidt, J.W., Matthes, F., Hatzopoulos, M., Böhm, K., Kemper, A., Grust, T., Böhm, C. (eds.) EDBT 2006. LNCS, vol. 3896, pp. 718–736. Springer, Heidelberg (2006)
Skopal, T.: Unified framework for fast exact and approximate search in dissimilarity spaces. ACM Transactions on Database Systems 32(4), 1–46 (2007)
Yi, B.-K., Jagadish, H.V., Faloutsos, C.: Efficient retrieval of similar time sequences under time warping. In: Proceedings of the Fourteenth International Conference on Data Engineering, ICDE 1998, pp. 201–208 (1998)
Zezula, P., Amato, G., Dohnal, V., Batko, M.: Similarity Search: The Metric Space Approach (Advances in Database Systems). Advances in Database Systems. Springer-Verlag New York, Inc., Secaucus (2005)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bartoš, T., Skopal, T. (2012). Revisiting Techniques for Lowerbounding the Dynamic Time Warping Distance. In: Navarro, G., Pestov, V. (eds) Similarity Search and Applications. SISAP 2012. Lecture Notes in Computer Science, vol 7404. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32153-5_14
Download citation
DOI: https://doi.org/10.1007/978-3-642-32153-5_14
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32152-8
Online ISBN: 978-3-642-32153-5
eBook Packages: Computer ScienceComputer Science (R0)