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

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

25
Total Citations
View Citations
541
Total Downloads

Downloads (Last 12 months)17
Downloads (Last 6 weeks)1

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
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
Zheng QWei RLi MWang XZhou DFu T(2021)Occupant’s lower extremities’ impact-based model calibration for vehicle under-belly blastStructural and Multidisciplinary Optimization10.1007/s00158-020-02668-363:1(391-405)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s00158-020-02668-3
Li MMao JQi XJin C(2020)A framework for cloned vehicle detectionFrontiers of Computer Science: Selected Publications from Chinese Universities10.1007/s11704-019-9005-414:5Online publication date: 1-Oct-2020
https://dl.acm.org/doi/10.1007/s11704-019-9005-4
Sanchez HBustos B(2020)A Multi-resolution Approximation for Time SeriesNeural Processing Letters10.1007/s11063-018-9929-y52:1(75-96)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1007/s11063-018-9929-y
Yeh CZhu YDau HDarvishzadeh ANoskov MKeogh ETeredesai AKumar VLi YRosales RTerzi EKarypis G(2019)Online Amnestic DTW to allow Real-Time Golden Batch MonitoringProceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining10.1145/3292500.3330650(2604-2612)Online publication date: 25-Jul-2019
https://dl.acm.org/doi/10.1145/3292500.3330650
Dan TLuo CLi YZhang C(2019)Trajectory Similarity Join for Spatial Temporal DatabaseDatabase and Expert Systems Applications10.1007/978-3-030-27618-8_23(306-321)Online publication date: 26-Aug-2019
https://dl.acm.org/doi/10.1007/978-3-030-27618-8_23
Mueen AChavoshi NAbu-El-Rub NHamooni HMinnich AMaccarthy J(2018)Speeding up dynamic time warping distance for sparse time series dataKnowledge and Information Systems10.1007/s10115-017-1119-054:1(237-263)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1007/s10115-017-1119-0
Xu YXie YFeng JLui JWang XWolf ALiu YHu C(2017)Correlation analysis between electricity consumption and economic developmentProceedings of the ACM Turing 50th Celebration Conference - China10.1145/3063955.3063973(1-6)Online publication date: 12-May-2017
https://dl.acm.org/doi/10.1145/3063955.3063973
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.

Media

Figures

Other

Tables

View Issue’s Table of Contents