License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SoCG.2016.6
URN: urn:nbn:de:0030-drops-58989
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5898/
Agarwal, Pankaj K. ;
Fox, Kyle ;
Pan, Jiangwei ;
Ying, Rex
Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences
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 near-linear time for point sequences drawn from k-packed or k-bounded curves, and subquadratic time for backbone sequences. Roughly speaking, a curve is k-packed if the length of its intersection with any ball of radius r is at most kr, and it is k-bounded if the sub-curve 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 minimum-weight 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 minimum-weight 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:1--6:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-009-5},
ISSN = {1868-8969},
year = {2016},
volume = {51},
editor = {S{\'a}ndor Fekete and Anna Lubiw},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5898},
URN = {urn:nbn:de:0030-drops-58989},
doi = {10.4230/LIPIcs.SoCG.2016.6},
annote = {Keywords: Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition}
}
|
Keywords: |
|
Dynamic time warping, Edit distance, Near-linear-time algorithm, Dynamic programming, Well-separated pair decomposition |
|
Collection: |
|
32nd International Symposium on Computational Geometry (SoCG 2016) |
|
Issue Date: |
|
2016 |
|
Date of publication: |
|
10.06.2016 |
