2020/10/11 by Matthieu Herrmann, Geoffrey I. Webb, Herrmann, Matthieu +1 · 1 citation
Computer Science · #37M10 #Advanced Text Analysis Techniques #Data Management and Algorithms #FOS: Computer and information sciences #Machine Learning (cs.LG) #Time Series Analysis and Forecasting
paper · pdf · doi:10.48550/arxiv.2010.05371
openalex publication_date 2020/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Dynamic Time Warping ("DTW") distance is widely used in time series analysis, be it for classification, clustering or similarity search. However, its quadratic time complexity prevents it from scaling. Strategies, based on early abandoning DTW or skipping its computation altogether thanks to lower bounds, have been developed for certain use cases such as nearest neighbour search. But vectorization and approximation aside, no advance was made on DTW itself until recently with the introduction of PrunedDTW. This algorithm, able to prune unpromising alignments, was later fitted with early abandoning. We present a new version of PrunedDTW, "EAPrunedDTW", designed with early abandon in mind from the start, and able to early abandon faster than before. We show that EAPrunedDTW significantly improves the computation time of similarity search in the UCR Suite, and renders lower bounds dispensable.