Abstract
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves π, σ in ℝ^d, it provides a robust, outlierinsensitive alternative to the Fréchet distance. However, like the Fréchet distance, the DTW distance is not invariant under translations. Can we efficiently optimize the DTW distance of π and σ under arbitrary translations, to compare the curves' shape irrespective of their absolute location?
There are surprisingly few works in this direction, which may be due to its computational intricacy: For the Euclidean norm, this problem contains as a special case the geometric median problem, which provably admits no exact algebraic algorithm (that is, no algorithm using only addition, multiplication, and kth roots). We thus investigate exact algorithms for nonEuclidean norms as well as approximation algorithms for the Euclidean norm.
For the L₁ norm in ℝ^d, we provide an 𝒪(n^{2(d+1)})time algorithm, i.e., an exact polynomialtime algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in ℝ², we show that a simple problemspecific insight leads to a (1+ε)approximation in time 𝒪(n³/ε²). We then show how to obtain a subcubic 𝒪̃(n^{2.5}/ε²) time algorithm with significant new ideas; this time comes close to the wellknown quadratic time barrier for computing DTW for fixed translations. Technically, the algorithm is obtained by speeding up repeated DTW distance estimations using a dynamic data structure for maintaining shortest paths in weighted planar digraphs. Crucially, we show how to traverse a candidate set of translations using spacefilling curves in a way that incurs only few updates to the data structure.
We hope that our results will facilitate the use of DTW under translation both in theory and practice, and inspire similar algorithmic approaches for related geometric optimization problems.
BibTeX  Entry
@InProceedings{bringmann_et_al:LIPIcs.SoCG.2022.20,
author = {Bringmann, Karl and Kisfaludi‑Bak, S\'{a}ndor and K\"{u}nnemann, Marvin and Marx, D\'{a}niel and Nusser, Andr\'{e}},
title = {{Dynamic Time Warping Under Translation: Approximation Guided by SpaceFilling Curves}},
booktitle = {38th International Symposium on Computational Geometry (SoCG 2022)},
pages = {20:120:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772273},
ISSN = {18688969},
year = {2022},
volume = {224},
editor = {Goaoc, Xavier and Kerber, Michael},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/16028},
URN = {urn:nbn:de:0030drops160287},
doi = {10.4230/LIPIcs.SoCG.2022.20},
annote = {Keywords: Dynamic Time Warping, Sequence Similarity Measures}
}
Keywords: 

Dynamic Time Warping, Sequence Similarity Measures 
Collection: 

38th International Symposium on Computational Geometry (SoCG 2022) 
Issue Date: 

2022 
Date of publication: 

01.06.2022 