TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 13.02.2020

isti-logo

Page Content

to Navigation

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.

 

 
Date
Speaker
Location
Language
13.02.2020
16:15
Vincent Froese
TEL 512
English

Back to the research colloquium site.

To top

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe