Binary Dynamic Time Warping in Linear Time

2021/01/04 by Kuszmaul, William
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.2101.01108

Abstract

Dynamic time warping distance (DTW) is a widely used distance measure between time series x, y ∈ Σⁿ. It was shown by Abboud, Backurs, and Williams that in the binary case, where |Σ| = 2, DTW can be computed in time O(n^1.87). We improve this running time O(n). Moreover, if x and y are run-length encoded, then there is an algorithm running in time O(k + ℓ), where k and ℓ are the number of runs in x and y, respectively. This improves on the previous best bound of O(kℓ) due to Dupont and Marteau.

Related

• Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
• Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings
• Making the Dynamic Time Warping Distance Warping-Invariant
• Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier
• Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings