An algorithm for improving lower bounds in dynamic time warping

Dynamic Time Warping (DTW) has been extensively used for time series data mining due to its robust performance across various domains. However, DTW is computationally expensive for many applications in practice. To mitigate this issue, lower bounds have been used as the basis for effective pruning strategies, significantly accelerating DTW computations for specific tasks. In this paper, we introduce an innovative algorithm called PDTW plugin, which employs the recently proposed Partial DTW (PDTW) and the segment reordering technique. This PDTW plugin can be integrated into most existing lower bounds to enhance their tightness and pruning effectiveness. The key insight of this work is to replace existing partial lower bounds with tighter PDTW plugin distance in order to achieve a higher pruning rate. Experimental results on four widely adopted existing lower bounds demonstrate that our approach significantly enhances their performance. Specifically, lower bounds incorporating the PDTW plugin achieve higher pruning rates across the majority of the 95 UCR Archive datasets in time series classification tasks. Moreover, on 53 of these datasets, using the lower bounds augmented with our plugin module achieves the fastest total runtime in classification. Notably, the proposed PDTW plugin provides considerable flexibility, easily integrates with existing lower bounds, and enables adjustments to the trade-off between pruning rate and computational cost.