Approximating dynamic time warping and edit distance for a pair of point sequences

DOI10.4230/LIPICS.SOCG.2016.6zbMATH Open1387.68226arXiv1512.01876OpenAlexW2963393865MaRDI QIDQ3132838FDOQ3132838

Authors: Kyle Fox, Jiangwei Pan, Rex Ying, Pankaj K. Agarwal 

Publication date: 30 January 2018

Abstract: We give the first subquadratic-time approximation schemes for dynamic time warping (DTW) and edit distance (ED) of several natural families of point sequences in $mathbb{R}^d$, for any fixed $dge1$. In particular, our algorithms compute $(1+varepsilon)$-approximations of DTW and ED in time near-linear for point sequences drawn from k-packed or k-bounded curves, and subquadratic for backbone sequences. Roughly speaking, a curve is $kappa$-packed if the length of its intersection with any ball of radius $r$ is at most $kappacdotr$, and a curve is $kappa$-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$. Our algorithms work by constructing a small set of rectangular regions that cover the entries of the dynamic programming table commonly used for these distance measures. The weights of entries inside each rectangle are roughly the same, so we are able to use efficient procedures to approximately compute the cheapest paths through these rectangles.

Full work available at URL: https://arxiv.org/abs/1512.01876

Recommendations

• Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
• Dynamic time warping and geometric edit distance: breaking the quadratic barrier
• Approximability of the discrete Fréchet distance
• Approximability of the discrete Fréchet distance

zbMATH Keywords

dynamic programmingedit distancedynamic time warpingwell-separated pair decompositionnear-linear-time algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (8)

• The one-way communication complexity of dynamic time warping distance
• Approximating the geometric edit distance
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Approximating the geometric edit distance
• Dynamic time warping and geometric edit distance: breaking the quadratic barrier
• Towards Efficient Interactive Computation of Dynamic Time Warping Distance
• Dynamic time warping under translation: approximation guided by space-filling curves
• Dynamic time warping under translation: approximation guided by space-filling curves

This page was built for publication: Approximating dynamic time warping and edit distance for a pair of point sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3132838)