A simple efficient approximation algorithm for dynamic time warping
Rex Ying, Jiangwei Pan, Kyle J. Fox, Pankaj K. Agarwal · 2016
Dynamic time warping (DTW) is a widely used curve similarity measure. We present a simple and efficient (1 + ε)- approximation algorithm for DTW between a pair of point sequences, say, P and Q, each of which is sampled from a curve. We prove that the running time of the algorithm is O([EQUATION]n log σ) for a pair of k-packed curves with a total of n points, assuming that the spreads of P and Q are bounded by σ. The spread of a point set is the ratio of the maximum to the minimum pairwise distance, and a curve is called K- packed if the length of its intersection with any disk of radius r is at most Kr. Although an algorithm with similar asymptotic time complexity was presented in [1], our algorithm is considerably simpler and more efficient in practice.