direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

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

Vincent Froese (TU Berlin)


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.We implemented and compared our algorithm to other methods in experiments.


Vincent Froese
TEL 512

Back to the research colloquium site.

To top

Zusatzinformationen / Extras