**Papers Published**

- Ying, R; Pan, J; Fox, K; Agarwal, PK,
*A simple efficient approximation algorithm for dynamic time warping*, GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems (October, 2016), ISBN 9781450345897

(last updated on 2018/07/20)**Abstract:**

© 2016 ACM. 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( κ 2 /∈ n log σ) for a pair of κ-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 κ-packed if the length of its intersection with any disk of radius r is at most κr. Although an algorithm with similar asymptotic time complexity was presented in [1], our algorithm is considerably simpler and more efficient in practice. We have implemented our algorithm. Our experiments on both synthetic and real-world data sets show that it is an order of magnitude faster than the standard exact DP algorithm on point sequences of length 5; 000 or more while keeping the approximation error within 5-10%. We demonstrate the eficacy of our algorithm by using it in two applications computing the k most similar trajectories to a query trajectory, and running the iterative closest point method for a pair of trajectories. We show that we can achieve 8-12 times speedup using our algorithm as a subroutine in these applications, without compromising much in accuracy.