Abstract
The problem of similarity search in time series database has attracted a lot of interest in the data mining field. DTW(Dynamic Time Warping) is a robust distance measure function for time series, which can handle time shifting and scaling. The main defect of DTW lies in its relatively high computational complexity of similarity search. In this paper, we develop a simple but efficient approximation technique for DTW to speed up the search process. Our method is based on a variation of the traditional histograms of the time series. This method can work with a time linear with the size of the database. In our experiment, we proved that the proposed technique is efficient and produces few false dismissals in most applications.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, R., Faloutsos, C., Swami, A.N.: Efficient similarity serach in sequence database. In: Proc. Conf.of Foundations of Data Organization and Algorithms (1993)
Agrawal, R., Lin, K.I., Sawhney, H.S., Shim, K.: Fast Similarity in the presence of noise, scaling, and translation in time-series databases. The VLDB Journal (1995)
Park, S., Chu, W.W., Yoon, J., Won, J.: Similarity search of time-warped subsequences via a suffix tree. Information Systems 28(7) (2003)
Chakrabarti, K., Garofalakis, M.N., Rastogi, R., Shim, K.: Approximate Query Processing Using Wavelets. The VLDB Journal (2000)
Kahveei, T., Singh, A.: Variable Length Queries for Time Series Data. In: Proc. of The ICDE (2001)
Chu, S., Keogh, E., Hart., D., Pazzani, M.: Iterative deepening dynamic time warping for time series. In: Proc. 2 SIAM International Conference on Data Mining
Yi, B.-K., Jagadish, H.V., Faloutsos, C.: Efficient Retrieval of Similar Time Sequences Under Time Warping. In: Proceedings of the 14th International Conference on Data Engineering (1998)
Kim, S.-W., Park, S.: An Index-Based Approach for Similarity Search Supporting Time Warping in Large Sequence Databases. In: ICDE (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gu, J., Jin, X. (2006). A Simple Approximation for Dynamic Time Warping Search in Large Time Series Database. In: Corchado, E., Yin, H., Botti, V., Fyfe, C. (eds) Intelligent Data Engineering and Automated Learning – IDEAL 2006. IDEAL 2006. Lecture Notes in Computer Science, vol 4224. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11875581_101
Download citation
DOI: https://doi.org/10.1007/11875581_101
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-45485-4
Online ISBN: 978-3-540-45487-8
eBook Packages: Computer ScienceComputer Science (R0)