Scaling Subsequence Similarity Join Based on Dynamic Time Warping

Subsequence similarity join is an important operation in time series analysis, widely employed for the identification of conserved or recurring patterns. Although Dynamic Time Warping (DTW) is widely recognized as an effective similarity measure due to its robustness to temporal distortions, its high computational cost has severely limited its applicability to large-scale subsequence similarity joins. To address this challenge, we propose an efficient DTW-based subsequence similarity join algorithm that significantly improves both time and space efficiency. Our approach improves upon the space complexity of the state-of-the-art method, enabling its scalable application on large datasets. Furthermore, we refine the DTW lower bounds by enhancing their effectiveness. Experimental results demonstrate that our CPU implementation achieves an average $7.80 \times$ speedup over existing approaches. Moreover, we present a GPU-accelerated variant that leverages massive parallelism to deliver up to two orders of magnitude speedup over our optimized CPU version, making DTW-based subsequence similarity join feasible at scale.