Math @ Duke

Publications [#318113] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Fox, K; Pan, J; Ying, R, Approximating dynamic time warping and edit distance for a pair of point sequences,
LIPIcs, vol. 51
(June, 2016),
pp. 6.16.16 [doi]
(last updated on 2018/02/22)
Abstract: © Pankaj K. Agarwal, Kyle Fox, Jiangwei Pan, and Rex Ying. We present the first subquadratic algorithms for computing similarity between a pair of point sequences in doublestruck R d , for any fixed d > 1, using dynamic time warping (DTW) and edit distance, assuming that the point sequences are drawn from certain natural families of curves. In particular, our algorithms compute (1 + ε)approximations of DTW and ED in nearlinear time for point sequences drawn from κpacked or κbounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is κpacked if the length of its intersection with any ball of radius r is at most κ · r, and it is κbounded if the subcurve between two curve points does not go too far from the two points compared to the distance between the two points. In backbone sequences, consecutive points are spaced at approximately equal distances apart, and no two points lie very close together. Recent results suggest that a subquadratic algorithm for DTW or ED is unlikely for an arbitrary pair of point sequences even for d = 1. The commonly used dynamic programming algorithms for these distance measures reduce the problem to computing a minimumweight path in a grid graph. Our algorithms work by constructing a small set of rectangular regions that cover the grid vertices. The weights of vertices inside each rectangle are roughly the same, and we develop efficient procedures to compute the approximate minimumweight paths through these rectangles.


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

