The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 7 of 143
Back to Result List

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(n2) 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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Vincent Froese, Brijnesh JainORCiD, Maciej Rymar, Mathias Welle
DOI:https://doi.org/10.1007/s00453-022-01038-3
Parent Title (English):Algorithmica
Publisher:Springer Nature
Document Type:Article
Language:English
Year of first Publication:2022
Release Date:2022/11/10
Pagenumber:17
Institutes:Fakultät Informatik und Mathematik
Begutachtungsstatus:peer-reviewed
research focus:Digitalisierung
OpenAccess Publikationsweg:Hybrid Open Access - OA-Veröffentlichung in einer Subskriptionszeitschrift/-medium
Licence (German):Creative Commons - CC BY - Namensnennung 4.0 International