Dynamic time warping shows strong limits for fast approximation

Fine-Grained Hardness of Approximating Dynamic Time Warping

Computational ComplexityData Structures and Algorithms

Summary

Dynamic time warping (DTW) is a way to measure similarity between sequences, like comparing speech or music patterns. This paper shows that even trying to approximate DTW quickly on certain types of sequences is very hard, based on well-known computer science assumptions. The authors prove that no fast algorithm can approximate DTW closely without taking nearly quadratic time in general. This means people aiming to speed up DTW computations face fundamental limitations.

What this means in practice

  • For algorithm designers: Avoid attempts to create fast near-exact DTW approximation algorithms on run-length encoded strings due to strong conditional hardness results.
  • For data compression engineers: Recognize the computational limits of approximating similarity measures like DTW when using run-length encoded data for fast comparison.

A theory result. No direct application yet.

Authors

Jihan Wang

Abstract

We prove conditional lower bounds for approximating dynamic time warping (DTW) over the uniform metric on three symbols. Let $N, M$ be the two string lengths and $n, m$ their respective numbers of runs. Under the Gap Block Disjointness (GBD) hypothesis, for every fixed $κ\in (0,1/6)$ and $δ\in (0,1)$, no deterministic algorithm $N^{κδ}$-approximates DTW on two explicit strings of length $N$ in $O(N^{2-δ})$ time. This matches the known tradeoff between approximation and running-time exponents for deterministic algorithms within any fixed factor greater than six in the approximation exponent. For run-length encoded strings, the Orthogonal Vectors Hypothesis (OVH) rules out any constant-factor approximation in $\widetilde{O}((nm)^{1-δ})$ time for every constant $δ>0$. More generally, for every fixed $η\in (0,1)$, it rules out $(N+M)^{1-η}$-approximation in the same running time. These bounds extend to every fixed metric with at least three points, including absolute distance on $\{0,1,2\}$. Both reductions use long runs to force equal-symbol matches in low-cost alignments. For explicit strings, we combine Boolean gadgets with deterministic gap amplification to obtain a polynomial approximation gap. For run-length encoded strings, an encoding of regular-expression membership gives accepting instances an alignment whose cost does not increase as selected runs grow. Rejecting instances have distance at least the chosen run length, while the number of runs stays fixed.