Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series

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 approximating or bounding the true DTW distance or considering special input data (e.g. binary or piecewise constant time series). In this paper, we present an exact algorithm to compute the DTW distance of two run-length encoded time series. The worst-case running time is cubic in the encoding length. In practice, however, our algorithm might be faster and used for accurate indexing and classification of time series in combination with preprocessing techniques such as piecewise aggregate approximation (PAA).