BlockDTW: Efficient and Scalable Similarity Search Algorithm for Healthcare-Focused Time-Series

Digital twins for engineering, finance, and especially personalized medicine often rely on time-series applications, such as computing the similarity between temporal signals. Dynamic Time Warping (DTW) remains the gold standard for robust alignment under temporal distortions, but its quadratic time and space complexity limits scalability and real-time usage. Existing methods such as FastDTW, PruneDTW, and SoftDTW attempt to address these issues, but often compromise on accuracy, differentiability, or flexibility. We introduce BlockDTW, a differentiable parallel approximation of DTW that divides time-series into non-overlapping blocks and computes local alignments. This reduces complexity to $\mathcal{O}(bN)$, enabling efficient training and inference. BlockDTW achieves good approximation relative to DTW with up to 8× speedup, as shown in three tasks: synthetic frequency-varying sinusoids, Trace dataset prediction with an FFNN, and EEG reconstruction using hvEEGNet. Results are comparable to SoftDTW and PruneDTW, with significantly lower runtime.