Dynamic Dynamic Time Warping
Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg · Society for Industrial and Applied Mathematics eBooks · 2024
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 Fréchet 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.