Approximating Dynamic Time Warping and Edit Distance for a Pair of Point Sequences

摘要: We give the first subquadratic-time approximation schemes for dynamic time warping (DTW) and edit distance (ED) of several natural families point sequences in $\mathbb{R}^d$, any fixed $d \ge 1$. In particular, our algorithms compute $(1+\varepsilon)$-approximations DTW ED near-linear drawn from k-packed or k-bounded curves, subquadratic backbone sequences. Roughly speaking, a curve is $\kappa$-packed if length its intersection with ball radius $r$ at most $\kappa \cdot r$, $\kappa$-bounded sub-curve between two points does not go too far compared to points. sequences, consecutive are spaced approximately equal distances apart, no lie very close together. Recent results suggest that algorithm unlikely an arbitrary pair even $d=1$. Our work by constructing small set rectangular regions cover entries programming table commonly used these measures. The weights inside each rectangle roughly same, so we able use efficient procedures cheapest paths through rectangles.