Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#323823] of Pankaj K. Agarwal

Papers Published

  1. 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/12)

    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320