Abstract
We present the first subquadratic algorithms for computing similarity between a pair of point sequences in 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 + eps)approximations of DTW and ED in nearlinear time for point sequences drawn from kpacked or kbounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is kpacked if the length of its intersection with any ball of radius r is at most kr, and it is kbounded 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.
BibTeX  Entry
@InProceedings{agarwal_et_al:LIPIcs:2016:5898,
author = {Pankaj K. Agarwal and Kyle Fox and Jiangwei Pan and Rex Ying},
title = {{Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences}},
booktitle = {32nd International Symposium on Computational Geometry (SoCG 2016)},
pages = {6:16:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770095},
ISSN = {18688969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5898},
URN = {urn:nbn:de:0030drops58989},
doi = {10.4230/LIPIcs.SoCG.2016.6},
annote = {Keywords: Dynamic time warping, Edit distance, Nearlineartime algorithm, Dynamic programming, Wellseparated pair decomposition}
}
Keywords: 

Dynamic time warping, Edit distance, Nearlineartime algorithm, Dynamic programming, Wellseparated pair decomposition 
Collection: 

32nd International Symposium on Computational Geometry (SoCG 2016) 
Issue Date: 

2016 
Date of publication: 

10.06.2016 