Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
Dynamic Time Warping Under Translation : Approximation Guided by Space-Filling Curves. / Bringmann, Karl; Kisfaludi-Bak, Sándor; Künnemann, Marvin; Marx, Dániel; Nusser, André.
38th International Symposium on Computational Geometry, SoCG 2022. ed. / Xavier Goaoc; Michael Kerber. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2022. 20 (Leibniz International Proceedings in Informatics, LIPIcs, Vol. 224).Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - Dynamic Time Warping Under Translation
T2 - 38th International Symposium on Computational Geometry, SoCG 2022
AU - Bringmann, Karl
AU - Kisfaludi-Bak, Sándor
AU - Künnemann, Marvin
AU - Marx, Dániel
AU - Nusser, André
N1 - Publisher Copyright: © Karl Bringmann, Sndor Kisfaludi-Bak, Marvin Knnemann, Dniel Marx, and Andr Nusser; licensed under Creative Commons License CC-BY 4.0
PY - 2022
Y1 - 2022
N2 - The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves p,s in Rd, it provides a robust, outlier-insensitive 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 p and s 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 k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L1 norm in Rd, we provide an O(n2(d+1))-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in R2, we show that a simple problem-specific insight leads to a (1 + e)-approximation in time O(n3/e2). We then show how to obtain a subcubic Oe(n2.5/e2) time algorithm with significant new ideas; this time comes close to the well-known 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 space-filling 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.
AB - The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves p,s in Rd, it provides a robust, outlier-insensitive 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 p and s 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 k-th roots). We thus investigate exact algorithms for non-Euclidean norms as well as approximation algorithms for the Euclidean norm. For the L1 norm in Rd, we provide an O(n2(d+1))-time algorithm, i.e., an exact polynomial-time algorithm for constant d. Here and below, n bounds the curves' complexities. For the Euclidean norm in R2, we show that a simple problem-specific insight leads to a (1 + e)-approximation in time O(n3/e2). We then show how to obtain a subcubic Oe(n2.5/e2) time algorithm with significant new ideas; this time comes close to the well-known 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 space-filling 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.
KW - Dynamic Time Warping
KW - Sequence Similarity Measures
U2 - 10.4230/LIPIcs.SoCG.2022.20
DO - 10.4230/LIPIcs.SoCG.2022.20
M3 - Article in proceedings
AN - SCOPUS:85134328735
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 38th International Symposium on Computational Geometry, SoCG 2022
A2 - Goaoc, Xavier
A2 - Kerber, Michael
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Y2 - 7 June 2022 through 10 June 2022
ER -
ID: 342673977