research-article

Anticipatory DTW for efficient similarity search in time series databases

Authors:

Marc Wichterich,

Thomas SeidlAuthors Info & Claims

Proceedings of the VLDB Endowment, Volume 2, Issue 1

Pages 826 - 837

https://doi.org/10.14778/1687627.1687721

Published: 01 August 2009 Publication History

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.

References

[1]

J. Aach and G. M. Church. Aligning gene expression time series with time warping algorithms. Bioinformatics, 17(6):495--508, 2001.

[2]

I. Assent and H. Kremer. Robust adaptable video copy detection. In SSTD. Springer, 2009.

Digital Library

[3]

I. Assent, A. Wenning, and T. Seidl. Approximation techniques for indexing the Earth Mover's Distance in multimedia databases. In ICDE, page 11, 2006.

Digital Library

[4]

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.

Digital Library

[5]

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.

[6]

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.

Digital Library

[7]

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.

[8]

L. Chen and R. Ng. On the marriage of Lp-norms and Edit Distance. In VLDB, pages 792--803, 2004.

Digital Library

[9]

S. Chu, E. J. Keogh, D. Hart, and M. J. Pazzani. Iterative deepening dynamic time warping for time series. In SDM, 2002.

[10]

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.

Digital Library

[11]

C. Faloutsos. Searching Multimedia Databases by Content. Kluwer Academic Publishers, 1996.

Digital Library

[12]

F. Itakura. Minimum prediction residual principle applied to speech recognition. IEEE Trans. Acoust., Speech, Signal Processing, 23(1):67--72, 1975.

[13]

M. W. Kadous. Australian sign language data set 1, 1999. www.cse.unsw.edu.au/~waleed/tml/data/.

[14]

E. J. Keogh. Exact indexing of dynamic time warping. In VLDB, pages 406--417, 2002.

Digital Library

[15]

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.

Digital Library

[16]

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.

[17]

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.

Digital Library

[18]

S. Kim, S. Park, and W. Chu. An index-based approach for similarity search supporting time warping in large sequence databases. In ICDE, 2001.

Digital Library

[19]

C. A. Ratanamahatana and E. J. Keogh. Making time-series classification more accurate using learned constraints. In SDM, 2004.

[20]

T. M. Rath and R. Manmatha. Lower-bounding of dynamic time warping distances for multivariate time series, 2003.

[21]

H. Sakoe and S. Chiba. Dynamic programming algorithm optimization for spoken word recognition. IEEE Trans. Acoust., Speech, Signal Processing, 26(1):43--49, 1978.

[22]

Y. Sakurai, C. Faloutsos, and M. Yamamuro. Stream monitoring under the time warping distance. In ICDE, pages 1046--1055, 2007.

[23]

Y. Sakurai, M. Yoshikawa, and C. Faloutsos. FTW: fast similarity search under the time warping distance. In PODS, pages 326--337, 2005.

Digital Library

[24]

S. Salvador and P. Chan. FastDTW: Toward accurate dynamic time warping in linear time and space. In KDD TDM, 2004.

[25]

S. Salvador and P. Chan. Toward accurate dynamic time warping in linear time and space. Intelligent Data Analysis, 11(5):561--580, 2007.

Digital Library

[26]

T. Seidl and H.-P. Kriegel. Optimal multi-step k-nearest neighbor search. In SIGMOD, pages 154--165. ACM, 1998.

Digital Library

[27]

A. F. Smeaton, P. Over, and W. Kraaij. Evaluation campaigns and trecvid. In Proc. MIR, 2006.

Digital Library

[28]

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.

Digital Library

[29]

B. K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In ICDE, pages 201--208, 1998.

Digital Library

[30]

M. Zhou and M. H. Wong. Boundary-based lower-bound functions for dynamic time warping and their indexing. In ICDE, pages 1307--1311, 2007.

[31]

M. Zhou and M. H. Wong. Efficient online subsequence searching in data streams under dynamic time warping distance. In ICDE, pages 686--695, 2008.

Digital Library

[32]

Y. Zhu and D. Shasha. Warping indexes with envelope transforms for query by humming. In SIGMOD, 2003.

Digital Library

Cited By

Cao CZhang WYang HRuan D(2025)Complementarity-Oriented Feature Fusion for Face-Phone Trajectory MatchingIEEE Access10.1109/ACCESS.2025.353110613(17911-17918)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3531106
Daiya DYadav MRao H(2024)Diffstock: Probabilistic Relational Stock Market Predictions Using Diffusion ModelsICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10446690(7335-7339)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10446690
Moustafa SKhodairy S(2024)Evaluating the concordance of Egyptian and international sunspot observationsPhysica Scripta10.1088/1402-4896/ad551799:7(075032)Online publication date: 19-Jun-2024
https://doi.org/10.1088/1402-4896/ad5517
Show More Cited By

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 Workshop

Similarity 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 management

Dynamic 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 Technology

In 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

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Proceedings of the VLDB Endowment

Proceedings of the VLDB Endowment Volume 2, Issue 1

August 2009

1293 pages

ISSN:2150-8097

Issue’s Table of Contents

Publisher

VLDB Endowment

Publication History

Published: 01 August 2009

Published in PVLDB Volume 2, Issue 1

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

54
Total Citations
View Citations
547
Total Downloads

Downloads (Last 12 months)18
Downloads (Last 6 weeks)3

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cao CZhang WYang HRuan D(2025)Complementarity-Oriented Feature Fusion for Face-Phone Trajectory MatchingIEEE Access10.1109/ACCESS.2025.353110613(17911-17918)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3531106
Daiya DYadav MRao H(2024)Diffstock: Probabilistic Relational Stock Market Predictions Using Diffusion ModelsICASSP 2024 - 2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)10.1109/ICASSP48485.2024.10446690(7335-7339)Online publication date: 14-Apr-2024
https://doi.org/10.1109/ICASSP48485.2024.10446690
Moustafa SKhodairy S(2024)Evaluating the concordance of Egyptian and international sunspot observationsPhysica Scripta10.1088/1402-4896/ad551799:7(075032)Online publication date: 19-Jun-2024
https://doi.org/10.1088/1402-4896/ad5517
Chen XGüttel S(2023)An Efficient Aggregation Method for the Symbolic Representation of Temporal DataACM Transactions on Knowledge Discovery from Data10.1145/353262217:1(1-22)Online publication date: 20-Feb-2023
https://dl.acm.org/doi/10.1145/3532622
Wang HLu YFu S(2023)The Similarity Recognition of Pilots’ Operational Action Sequence Based on Blocked Dynamic Time Warping during a Flight MissionEngineering Psychology and Cognitive Ergonomics10.1007/978-3-031-35392-5_20(253-263)Online publication date: 23-Jul-2023
https://dl.acm.org/doi/10.1007/978-3-031-35392-5_20
Stübinger JWalter D(2022)Using Multi-Dimensional Dynamic Time Warping to Identify Time-Varying Lead-Lag RelationshipsSensors10.3390/s2218688422:18(6884)Online publication date: 12-Sep-2022
https://doi.org/10.3390/s22186884
Zheng QWu MSun XWang XFu TZhou D(2022)Combined Bayesian and error assessment-based model calibration method for vehicle under-belly blast with uncertaintyStructural and Multidisciplinary Optimization10.1007/s00158-022-03226-965:5Online publication date: 12-Apr-2022
https://doi.org/10.1007/s00158-022-03226-9
Iyer SMahajan A(2021)Predicting total electron content in ionosphere using vector autoregression model during geomagnetic stormJournal of Applied Geodesy10.1515/jag-2021-001515:4(279-291)Online publication date: 23-Jun-2021
https://doi.org/10.1515/jag-2021-0015
Zhang ZLi DZhang ZDuffield N(2021)A time-series clustering algorithm for analyzing the changes of mobility pattern caused by COVID-19Proceedings of the 1st ACM SIGSPATIAL International Workshop on Animal Movement Ecology and Human Mobility10.1145/3486637.3489489(13-17)Online publication date: 2-Nov-2021
https://dl.acm.org/doi/10.1145/3486637.3489489
Chen XGuttel S(2021)A fast sorting-based aggregation method for symbolic time series representation2021 International Conference on Data Mining Workshops (ICDMW)10.1109/ICDMW53433.2021.00131(1009-1016)Online publication date: Dec-2021
https://doi.org/10.1109/ICDMW53433.2021.00131
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents