Dynamic Dynamic Time Warping

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(n^2) time in constant dimension. This
tightly matches a SETH-based lower bound, even for curves in R^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(n^{1.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 R^1, there is no dynamic algorithm to maintain
the DTW distance with update and query time O(n^{1.5 - \delta}) for
any constant \delta > 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.

Joint work with:
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Tomasz Kociumaka, Eva Rotenberg