Math @ Duke

Publications [#323823] of Pankaj K. Agarwal
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 [doi]
(last updated on 2017/12/14)
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 realworld 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 510%. 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 812 times speedup using our algorithm as a subroutine in these applications, without compromising much in accuracy.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

