Ira Assent
Thomas Seidl
Abstract
Time series arise in many different applications in the form of sensor data, stocks data, videos, and other time-related information. Analysis of this data typically requires searching for similar time series in a database. Dynamic Time Warping (DTW) is a widely used high-quality distance measure for time series. As DTW is computationally expensive, efficient algorithms for fast computation are crucial.
In this paper, we propose a novel filter-and-refine DTW algorithm called Anticipatory DTW. Existing algorithms aim at efficiently finding similar time series by filtering the database and computing the DTW in the refinement step. Unlike these algorithms, our approach exploits previously unused information from the filter step during the refinement, allowing for faster rejection of false candidates. We characterize a class of applicable filters for our approach, which comprises state-of-the-art lower bounds of the DTW.
Our novel anticipatory pruning incurs hardly any over-head and no false dismissals. We demonstrate substantial efficiency improvements in thorough experiments on synthetic and real world time series databases and show that our technique is highly scalable to multivariate, long time series and wide DTW bands.
- J. Aach and G. M. Church. Aligning gene expression time series with time warping algorithms. Bioinformatics, 17(6):495--508, 2001.Google Scholar
Cross Ref
- I. Assent and H. Kremer. Robust adaptable video copy detection. In SSTD. Springer, 2009. Google ScholarDigital Library
- I. Assent, A. Wenning, and T. Seidl. Approximation techniques for indexing the Earth Mover's Distance in multimedia databases. In ICDE, page 11, 2006. Google ScholarDigital Library
- V. Athitsos, P. Papapetrou, M. Potamias, G. Kollios, and D. Gunopulos. Approximate embedding-based subsequence matching of time series. In SIGMOD, pages 365--378, 2008. Google ScholarDigital Library
- D. J. Berndt and J. Clifford. Using dynamic time warping to find patterns in time series. In AAAI Workshop on KDD, pages 229--248, 1994.Google Scholar
- F. K.-P. Chan, A. W.-C. Fu, and C. Yu. Haar wavelets for efficient similarity search of time-series: With and without time warping. TKDE, 15(3):686--705, 2003. Google ScholarDigital Library
- A.-P. Chen, S.-F. Lin, and Y.-C. Cheng. Time registration of two image sequences by dynamic time warping. In Proc. ICNSC, pages 418--423, 2004.Google Scholar
- L. Chen and R. Ng. On the marriage of Lp-norms and Edit Distance. In VLDB, pages 792--803, 2004. Google ScholarDigital Library
- S. Chu, E. J. Keogh, D. Hart, and M. J. Pazzani. Iterative deepening dynamic time warping for time series. In SDM, 2002.Google ScholarCross Ref
- H. Ding, G. Trajcevski, P. Scheuermann, X. Wang, and E. Keogh. Querying and mining of time series data: Experimental comparison of representations and distance measures. In VLDB, 2008. Google ScholarDigital Library
- C. Faloutsos. Searching Multimedia Databases by Content. Kluwer Academic Publishers, 1996. Google ScholarDigital Library
- F. Itakura. Minimum prediction residual principle applied to speech recognition. IEEE Trans. Acoust., Speech, Signal Processing, 23(1):67--72, 1975.Google ScholarCross Ref
- M. W. Kadous. Australian sign language data set 1, 1999. www.cse.unsw.edu.au/~waleed/tml/data/.Google Scholar
- E. J. Keogh. Exact indexing of dynamic time warping. In VLDB, pages 406--417, 2002. Google ScholarDigital Library
- E. J. Keogh, K. Chakrabarti, M. Pazzani, and S. Mehrotra. Locally adaptive dimensionality reduction for indexing large time series databases. SIGMOD Rec., 30(2):151--162, 2000. Google ScholarDigital Library
- E. J. Keogh, K. Chakrabarti, M. J. Pazzani, and S. Mehrotra. Dimensionality reduction for fast similarity search in large time series databases. KAIS, 3(3):263--286, 2001.Google ScholarCross Ref
- 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, pages 882--893, 2006. Google ScholarDigital Library
- S. Kim, S. Park, and W. Chu. An index-based approach for similarity search supporting time warping in large sequence databases. In ICDE, 2001. Google ScholarDigital Library
- C. A. Ratanamahatana and E. J. Keogh. Making time-series classification more accurate using learned constraints. In SDM, 2004.Google ScholarCross Ref
- T. M. Rath and R. Manmatha. Lower-bounding of dynamic time warping distances for multivariate time series, 2003.Google Scholar
- H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust., Speech, Signal Processing, 26(1):43--49, 1978.Google ScholarCross Ref
- Y. Sakurai, C. Faloutsos, and M. Yamamuro. Stream monitoring under the time warping distance. In ICDE, pages 1046--1055, 2007.Google ScholarCross Ref
- Y. Sakurai, M. Yoshikawa, and C. Faloutsos. FTW: fast similarity search under the time warping distance. In PODS, pages 326--337, 2005. Google ScholarDigital Library
- S. Salvador and P. Chan. FastDTW: Toward accurate dynamic time warping in linear time and space. In KDD TDM, 2004.Google Scholar
- S. Salvador and P. Chan. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561--580, 2007. Google ScholarDigital Library
- T. Seidl and H.-P. Kriegel. Optimal multi-step k-nearest neighbor search. In SIGMOD, pages 154--165. ACM, 1998. Google ScholarDigital Library
- A. F. Smeaton, P. Over, and W. Kraaij. Evaluation campaigns and trecvid. In Proc. MIR, 2006. Google ScholarDigital Library
- M. Vlachos, M. Hadjieleftheriou, D. Gunopulos, and E. J. Keogh. Indexing multi-dimensional time-series with support for multiple distance measures. In SIGKDD, pages 216--225, 2003. Google ScholarDigital Library
- B. K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In ICDE, pages 201--208, 1998. Google ScholarDigital Library
- M. Zhou and M. H. Wong. Boundary-based lower-bound functions for dynamic time warping and their indexing. In ICDE, pages 1307--1311, 2007.Google ScholarCross Ref
- M. Zhou and M. H. Wong. Efficient online subsequence searching in data streams under dynamic time warping distance. In ICDE, pages 686--695, 2008. Google ScholarDigital Library
- Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In SIGMOD, 2003. Google ScholarDigital Library
Index Terms
- Anticipatory DTW for efficient similarity search in time series databases
Recommendations
Similarity search for time series based on efficient warping measure
DM-IKM '12: Proceedings of the Data Mining and Intelligent Knowledge Management WorkshopSimilarity search is one of the most important tasks in time series data mining, and similarity measure between time series is a basic work. Dynamic time warping (DTW) is often used to compute distance between two time series by warping time axes to ...
Efficient processing of multiple DTW queries in time series databases
SSDBM'11: Proceedings of the 23rd international conference on Scientific and statistical database managementDynamic Time Warping (DTW) is a widely used distance measure for time series that has been successfully used in science and many other application domains. As DTW is computationally expensive, there is a strong need for efficient query processing ...
Comparing three lower bounding methods for DTW in time series classification
SoICT '12: Proceedings of the 3rd Symposium on Information and Communication TechnologyIn comparison to Euclidean distance, Dynamic Time Warping (DTW) is a much more robust distance measure for time series data. For speeding up DTW computation, a few lower bounding techniques have been proposed in literature to guarantee no false ...
Comments