A simple efficient approximation algorithm for dynamic time warping


Conference Paper

© 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.

Full Text

Duke Authors

Cited Authors

  • Ying, R; Pan, J; Fox, K; Agarwal, PK

Published Date

  • October 31, 2016

Published In

  • Gis: Proceedings of the Acm International Symposium on Advances in Geographic Information Systems

International Standard Book Number 13 (ISBN-13)

  • 9781450345897

Digital Object Identifier (DOI)

  • 10.1145/2996913.2996954

Citation Source

  • Scopus