Metraipolis › archive › dc_dacebc82141b

Dynamic Time Warping in the Low-Distance Regime — arXiv:2609.40249

Source: arXiv (en)
Original: https://arxiv.org/abs/2609.40249
License (as archived): CC0-1.0
Archived: 2026-10-07T15:17:13.884Z
SHA-256 of the archived text: aaf385fe2d1016297bdfdb0eea52fb0f79ca6335130321f9b63699e44d2e275a
Stable URL of this page: https://metraipolis.com/documento/dc_dacebc82141b

How to cite

Dynamic Time Warping in the Low-Distance Regime — arXiv:2609.40249 — arXiv (en), https://arxiv.org/abs/2609.40249 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_dacebc82141b (Metraipolis archive dc_dacebc82141b, sha256 aaf385fe2d1016297bdfdb0eea52fb0f79ca6335130321f9b63699e44d2e275a)

BibTeX

@misc{dcdacebc82141b,
  title = {Dynamic Time Warping in the Low-Distance Regime — arXiv:2609.40249},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.40249},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_dacebc82141b; sha256 aaf385fe2d1016297bdfdb0eea52fb0f79ca6335130321f9b63699e44d2e275a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.40249. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Dynamic Time Warping (DTW) is a classical similarity measure for strings and time series that allows local stretching. Given non-empty strings $S,T$ over an alphabet $\Sigma$ and a cost function $\delta:\Sigma^2\to\mathbb{R}_{\ge0}$, $DTW_\delta(S,T)$ is the minimum total cost of equal-length expansions of $S$ and $T$ obtained by duplicating characters. For strings of length at most $n$, DTW is computable in $O(n^2)$ time, and this is conditionally optimal under the Orthogonal Vectors Hypothesis (OVH). We study the low-distance regime, where an integer $k$ upper-bounds $DTW_\delta(S,T)$, assuming $\delta(a,a)=0$ and $\delta(a,b)\ge1$ for $a\ne b$. For several classical similarity measures, this regime admits $O(n+\operatorname{poly}(k))$ algorithms, whereas for DTW with metric costs the best known bound is $O(nk)$. We show that this dependence is essentially optimal: assuming OVH, computing DTW requires $n^{1-o(1)}k$ time even for the discrete mismatch-cost function, which assigns cost $1$ to every mismatch. The lower bound applies to the whole spectrum of thresholds $k$ between constant and linear in $n$. Our reduction from Orthogonal Vectors encodes vector coordinates in the lengths of equal-character runs. The resulting instances are very structured: collapsing runs to single characters reveals long substrings with short periods. We complement the lower bound with a $\tilde O(n+\operatorname{poly}(k))$-time algorithm whenever, after collapsing runs in the inputs, every substring with period $O(k)$ has length $\operatorname{poly}(k)$. Finally, we extend this lower bound to DTW pattern matching, which asks whether any non-empty substring of a length-$n$ text has DTW distance at most $k$ from a length-$m$ pattern. We prove that the classic $O(nm)$-time dynamic-programming algorithm is near-optimal under OVH, even when $k=O(\log n)$.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-10-01 in cs.DS).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.40249 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-07T14:50:37.657Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-10-01?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).