# Dynamic Dynamic Time Warping

arXiv: https://arxiv.org/abs/2310.18128 · HTML: https://mlsanity.com/paper/2310.18128/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 Oct 2023.

## Built on by (most cited first, 5 of 5)

- [A Survey: Spatiotemporal Consistency in Video Generation](https://mlsanity.com/paper/2502.17863/) (2025)
- [Generative Adversarial Network based Voice Conversion: Techniques, Challenges, and Recent Advancements](https://mlsanity.com/paper/2504.19197/) (2025)
- [Resource Constrained Pathfinding with A* and Negative Weights](https://mlsanity.com/paper/2503.11037/) (2025)
- [Animation2Code: Evaluating Temporal Visual Reasoning in Video-to-Code Generation](https://mlsanity.com/paper/2606.28593/) (2026)
- [Geometry-Conditioned Fixed-Scaffold Encoders for Time-Warp Robust Sequence Retrieval](https://mlsanity.com/paper/2609.36809/) (2026)

## Abstract (arXiv)

The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, especially for temporal data, and is known to be a robust, outlier-insensitive alternative to the frechet distance. For static curves of at most n points, the DTW distance can be computed in O(n2) time in constant dimension. This tightly matches a SETH-based lower bound, even for curves in ℝ1. In this work, we study dynamic algorithms for the DTW distance. Here, the goal is to design a data structure that can be efficiently updated to accommodate local changes to one or both curves, such as inserting or deleting vertices and, after each operation, reports the updated DTW distance. We give such a data structure with update and query time O(n1.5 log n), where n is the maximum length of the curves. As our main result, we prove that our data structure is conditionally optimal, up to subpolynomial factors. More precisely, we prove that, already for curves in ℝ1, there is no dynamic algorithm to maintain the DTW distance with update and query time~makeboxO(n1.5 - δ) for any constant δ > 0, unless the Negative-k-Clique Hypothesis fails. In fact, we give matching upper and lower bounds for various trade-offs between update and query time, even in cases where the lengths of the curves differ.