  Dynamic Time Warping (DTW) is a well-known similarity measure for time
series. The standard dynamic programming approach to compute the DTW distance
of two length-$n$ time series, however, requires~$O(n^2)$ time, which is often
too slow for real-world applications. Therefore, many heuristics have been
proposed to speed up the DTW computation. These are often based on lower
bounding techniques, approximating the DTW distance, or considering special
input data such as binary or piecewise constant time series. In this paper, we
present a first exact algorithm to compute the DTW distance of two run-length
encoded time series whose running time only depends on the encoding lengths of
the inputs. The worst-case running time is cubic in the encoding length. In
experiments we show that our algorithm is indeed fast for time series with
short encoding lengths.
