  Dynamic Time Warping (DTW) is a widely used similarity measure for comparing
strings that encode time series data, with applications to areas including
bioinformatics, signature verification, and speech recognition. The standard
dynamic-programming algorithm for DTW takes $O(n^2)$ time, and there are
conditional lower bounds showing that no algorithm can do substantially better.
  In many applications, however, the strings $x$ and $y$ may contain long runs
of repeated letters, meaning that they can be compressed using run-length
encoding. A natural question is whether the DTW-distance between these
compressed strings can be computed efficiently in terms of the lengths $k$ and
$\ell$ of the compressed strings. Recent work has shown how to achieve
$O(k\ell^2 + \ell k^2)$ time, leaving open the question of whether a
near-quadratic $\tilde{O}(k\ell)$-time algorithm might exist.
  We show that, if a small approximation loss is permitted, then a
near-quadratic time algorithm is indeed possible: our algorithm computes a $(1
+ \epsilon)$-approximation for $DTW(x, y)$ in $\tilde{O}(k\ell / \epsilon^3)$
time, where $k$ and $\ell$ are the number of runs in $x$ and $y$. Our algorithm
allows for $DTW$ to be computed over any metric space $(\Sigma, \delta)$ in
which distances are $O(log(n))$-bit integers. Surprisingly, the algorithm also
works even if $\delta$ does not induce a metric space on $\Sigma$ (e.g.,
$\delta$ need not satisfy the triangle inequality).
