Early Abandoning PrunedDTW and its application to similarity search
This work addresses the computational bottleneck for researchers and practitioners in time series analysis, offering an incremental improvement over existing methods.
The paper tackles the scalability issue of Dynamic Time Warping (DTW) in time series analysis by introducing EAPrunedDTW, a new algorithm that integrates early abandoning from the start, resulting in significantly faster computation times for similarity search in the UCR Suite and making lower bounds unnecessary.
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.