Fast exact dynamic time warping on run-length encoded time series

DOI10.1007/S00453-022-01038-3MaRDI QIDQ2684485zbMATH OpenOpenAlexFDO

Authors Vincent Froese, Brijnesh J. Jain, Maciej Rymar, Mathias Weller

Publication date 16 February 2023

Published in Algorithmica (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1903.03003

zbMATH Keywords

block matrixline intersectionssparse datatime series similarity

Mathematics Subject Classification ID

Time series, auto-correlation, regression, etc. in statistics (GARCH) (62M10) Analysis of algorithms (68W40)

Abstract: 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.

Recommendations

• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• scientific article; zbMATH DE number 7651119
• Exact mean computation in dynamic time warping spaces
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Fast and exact warping of time series using adaptive segmental approximations
• Approximating length-restricted means under dynamic time warping

Cites work

• A fully compressed algorithm for computing the edit distance of run-length encoded strings
• Dimensionality reduction for fast similarity search in large time series databases
• Dynamic programming algorithm optimization for spoken word recognition
• Dynamic time warping and geometric edit distance: breaking the quadratic barrier
• Dynamic Time Warping in Strongly Subquadratic Time: Algorithms for the Low-Distance Regime and Approximate Evaluation
• Faster STR-EC-LCS computation
• RLE edit distance in near optimal time
• Speeding up similarity search under dynamic time warping by pruning unpromising alignments
• Which problems have strongly exponential complexity?

Cited in

(13)

• Speeding up similarity search under dynamic time warping by pruning unpromising alignments
• Fast and exact warping of time series using adaptive segmental approximations
• A faster reduction of the dynamic time warping distance to the longest increasing subsequence length
• Exact mean computation in dynamic time warping spaces
• Faster retrieval with a two-pass dynamic-time-warping lower bound
• Dynamic time warping and geometric edit distance: breaking the quadratic barrier
• Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
• The one-way communication complexity of dynamic time warping distance
• Pattern matching under DTW distance
• Towards Efficient Interactive Computation of Dynamic Time Warping Distance
• On computing exact means of time series using the move-split-merge metric
• Computing continuous dynamic time warping of time series in polynomial time
• Õptimal dynamic time warping on run-length encoded strings

This page was built for publication: Fast exact dynamic time warping on run-length encoded time series

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2684485)