Editing Dynamic time warping (section)

==Fast computation==

Fast techniques for computing DTW include PrunedDTW,<ref>Silva, D. F., Batista, G. E. A. P. A. (2015). [http://sites.labic.icmc.usp.br/dfs/pdf/SDM_PrunedDTW.pdf Speeding Up All-Pairwise Dynamic Time Warping Matrix Calculation].</ref> SparseDTW,<ref>	
Al-Naymat, G., Chawla, S., Taheri, J. (2012). [https://arxiv.org/abs/1201.2969 SparseDTW: A Novel Approach to Speed up Dynamic Time Warping].</ref> FastDTW,<ref>Stan Salvador, Philip Chan, FastDTW: Toward Accurate Dynamic Time Warping in Linear Time and Space. KDD Workshop on Mining Temporal and Sequential Data, pp. 70–80, 2004.</ref> and the MultiscaleDTW.<ref>Meinard Müller, Henning Mattes, and Frank Kurth (2006). [https://www.audiolabs-erlangen.de/fau/professor/mueller/publications/2006_MuellerMattesKurth_MultiscaleAudioSynchronization_ISMIR.pdf An Efficient Multiscale Approach to Audio Synchronization]. Proceedings of the International Conference on Music Information Retrieval (ISMIR), pp. 192—197.</ref><ref>Thomas Prätzlich, Jonathan Driedger, and Meinard Müller (2016). Memory-Restricted Multiscale Dynamic Time Warping. Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), pp. 569—573.</ref>

A common task, retrieval of similar time series, can be accelerated by using lower bounds such as LB_Keogh,<ref>{{cite journal | last1 = Keogh | first1 = E. | last2 = Ratanamahatana | first2 = C. A. | year = 2005 | title = Exact indexing of dynamic time warping | journal = Knowledge and Information Systems | volume = 7 | issue = 3| pages = 358–386 | doi=10.1007/s10115-004-0154-9| s2cid = 207056701 }}</ref> LB_Improved,<ref>{{cite journal | last1 = Lemire | first1 = D. | year = 2009 | title = Faster Retrieval with a Two-Pass Dynamic-Time-Warping Lower Bound | arxiv = 0811.3301| journal = Pattern Recognition | volume = 42 | issue = 9| pages = 2169–2180 | doi=10.1016/j.patcog.2008.11.030| bibcode = 2009PatRe..42.2169L | s2cid = 8658213 }}</ref> or LB_Petitjean.<ref name="TightLB">{{cite journal |last1=Webb |first1=Geoffrey I. |last2=Petitjean |first2=Francois |title=Tight lower bounds for Dynamic Time Warping |journal=Pattern Recognition |date=2021 |volume=115 |page=107895 |doi=10.1016/j.patcog.2021.107895 |arxiv=2102.07076 |bibcode=2021PatRe.11507895W |s2cid=231925247 }}</ref> However, the Early Abandon and Pruned DTW algorithm reduces the degree of acceleration that lower bounding provides and sometimes renders it ineffective.

In a survey, Wang et al. reported slightly better results with the LB_Improved lower bound than the LB_Keogh bound, and found that other techniques were inefficient.<ref>{{cite journal | last1 = Wang | first1 = Xiaoyue | display-authors = etal   | year = 2010| title = Experimental comparison of representation methods and distance measures for time series data | journal = Data Mining and Knowledge Discovery | volume = 2010 | pages = 1–35 | arxiv = 1012.2789 }}</ref> Subsequent to this survey, the LB_Enhanced bound was developed that is always tighter than LB_Keogh while also being more efficient to compute.<ref name="LBEnhanced">{{cite book |last1=Tan |first1=Chang Wei |last2=Petitjean |first2=Francois |last3=Webb |first3=Geoffrey I. |chapter=Elastic bands across the path: A new framework and method to lower bound DTW |title=Proceedings of the 2019 SIAM International Conference on Data Mining |date=2019 |pages=522–530 |doi=10.1137/1.9781611975673.59 |arxiv=1808.09617 |isbn=978-1-61197-567-3 |s2cid=52120426 }}</ref>  LB_Petitjean is the tightest known lower bound that can be computed in linear time.<ref name="TightLB" />