Segmental DTW: Parallelizable Alternative to Dynamic Time Warping for Audio Alignment

Dynamic Time Warping (DTW) is a classic algorithm for aligning two temporal sequences, but its O(N²) compute and memory costs make it impractical for large datasets. Previous optimizations—band constraints or multiresolution—still preserve sequential dependencies, limiting parallelism. In this paper, TJ Tsai proposes Segmental DTW, a new approach that exploits the abundance of modern parallel compute by breaking the alignment problem into independent subproblems. The global cost matrix is partitioned into smaller sub-matrices, each processed with subsequence DTW in parallel. A segment-level dynamic programming step then stitches these local alignments into a globally optimal path.

Two variants are presented: one where sub-matrices overlap and one where they are disjoint. The author shows both closely match regular DTW accuracy on the Chopin Mazurka audio alignment dataset. Critically, nearly all computations are parallelizable, and one variant is unilaterally better in both theory and practice. Published at ICASSP 2021, this work offers a practical path to scaling DTW for real-time applications in speech processing, music retrieval, and gesture recognition—where sequence alignment is fundamental but speed matters.