Segmental DTW: A Parallelizable Alternative to Dynamic Time Warping
Sound
Summary
The authors study ways to speed up a popular technique called DTW, which is used to match sequences but usually takes a lot of time because it works step-by-step. They introduce Segmental DTW, which splits the large problem into smaller parts that can be solved at the same time, then combines these results for a global match. Their tests on music data show this new method works almost as well as the traditional DTW but can be done much faster because it allows parallel computing. Between two versions they test, one performs better both in practice and in theory.
Authors
TJ Tsai
Abstract
In this work we explore parallelizable alternatives to DTW for globally aligning two feature sequences. One of the main practical limitations of DTW is its quadratic computation and memory cost. Previous works have sought to reduce the computational cost in various ways, such as imposing bands in the cost matrix or using a multiresolution approach. In this work, we utilize the fact that computation is an abundant resource and focus instead on exploring alternatives that approximate the inherently sequential DTW algorithm with one that is parallelizable. We describe two variations of an algorithm called Segmental DTW, in which the global cost matrix is broken into smaller sub-matrices, subsequence DTW is performed on each sub-matrix, and the results are used to solve a segment-level dynamic programming problem that specifies a globally optimal alignment path. We evaluate the proposed alignment algorithms on an audio-audio alignment task using the Chopin Mazurka dataset, and we show that they closely match the performance of regular DTW. We further demonstrate that almost all of the computations in Segmental DTW are parallelizable, and that one of the variants is unilaterally better than the other for both empirical and theoretical reasons.