{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T16:01:27Z","timestamp":1778601687743,"version":"3.51.4"},"reference-count":32,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.14778\/1687627.1687721","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"826-837","source":"Crossref","is-referenced-by-count":50,"title":["Anticipatory DTW for efficient similarity search in time series databases"],"prefix":"10.14778","volume":"2","author":[{"given":"Ira","family":"Assent","sequence":"first","affiliation":[{"name":"Aalborg University, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marc","family":"Wichterich","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ralph","family":"Krieger","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hardy","family":"Kremer","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Seidl","sequence":"additional","affiliation":[{"name":"RWTH Aachen University, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.6.495"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02982-0_25"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.25"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376656"},{"key":"e_1_2_1_5_1","first-page":"229","volume-title":"AAAI Workshop on KDD","author":"Berndt D. J.","year":"1994","unstructured":"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 . 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."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198399"},{"key":"e_1_2_1_7_1","first-page":"418","volume-title":"Proc. ICNSC","author":"Chen A.-P.","year":"2004","unstructured":"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 . 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."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316758"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972726.12"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454226"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/524590"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1975.1162641"},{"key":"e_1_2_1_13_1","volume-title":"Australian sign language data set 1","author":"Kadous M. W.","year":"1999","unstructured":"M. W. Kadous . Australian sign language data set 1 , 1999 . www.cse.unsw.edu.au\/~waleed\/tml\/data\/. M. W. Kadous. Australian sign language data set 1, 1999. www.cse.unsw.edu.au\/~waleed\/tml\/data\/."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1287369.1287405"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/376284.375680"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011669"},{"key":"e_1_2_1_17_1","first-page":"882","volume-title":"VLDB","author":"Keogh E. J.","year":"2006","unstructured":"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 . 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."},{"key":"e_1_2_1_18_1","volume-title":"ICDE","author":"Kim S.","year":"2001","unstructured":"S. Kim , S. Park , and W. Chu . An index-based approach for similarity search supporting time warping in large sequence databases . In ICDE , 2001 . S. Kim, S. Park, and W. Chu. An index-based approach for similarity search supporting time warping in large sequence databases. In ICDE, 2001."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972740.2"},{"key":"e_1_2_1_20_1","volume-title":"Lower-bounding of dynamic time warping distances for multivariate time series","author":"Rath T. M.","year":"2003","unstructured":"T. M. Rath and R. Manmatha . Lower-bounding of dynamic time warping distances for multivariate time series , 2003 . T. M. Rath and R. Manmatha. Lower-bounding of dynamic time warping distances for multivariate time series, 2003."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASSP.1978.1163055"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368963"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065210"},{"key":"e_1_2_1_24_1","volume-title":"KDD TDM","author":"Salvador S.","year":"2004","unstructured":"S. Salvador and P. Chan . FastDTW: Toward accurate dynamic time warping in linear time and space . In KDD TDM , 2004 . S. Salvador and P. Chan. FastDTW: Toward accurate dynamic time warping in linear time and space. In KDD TDM, 2004."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/1367985.1367993"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276319"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1178677.1178722"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956777"},{"key":"e_1_2_1_29_1","first-page":"201","volume-title":"ICDE","author":"Yi B. K.","year":"1998","unstructured":"B. K. Yi , H. V. Jagadish , and C. Faloutsos . Efficient retrieval of similar time sequences under time warping . In ICDE , pages 201 -- 208 , 1998 . B. K. Yi, H. V. Jagadish, and C. Faloutsos. Efficient retrieval of similar time sequences under time warping. In ICDE, pages 201--208, 1998."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368999"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497477"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872780"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687721","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:32:28Z","timestamp":1672227148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687721"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":32,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687721"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687721","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}