Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Access rights
openAccess
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Other link related to publication (opens in new window)
Date
2022-06-01
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
17
1-17
1-17
Series
38th International Symposium on Computational Geometry, SoCG 2022, Leibniz International Proceedings in Informatics, LIPIcs, Volume 224
Abstract
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.Description
Funding Information: Karl Bringmann: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979). Sándor Kisfaludi-Bak: Part of this research was conducted while the author was at the Max Planck Institute for Informatics, and part of it while he was at the Institute for Theoretical Studies, ETH Zürich. Funding Information: Marvin Künnemann: Research supported by Dr. Max Rössler, by the Walter Haefner Foundation, and by the ETH Zürich Foundation. Dániel Marx: Research supported by the European Research Council (ERC) consolidator grant No. 725978 SYSTEMATICGRAPH. André Nusser: Part of this research was conducted while the author was at Saarbrücken Graduate School of Computer Science and Max Planck Institute for Informatics. The author is supported by the VILLUM Foundation grant 16582. Funding Information: Funding Karl Bringmann: This work is part of the project TIPEA that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (grant agreement No. 850979). Sándor Kisfaludi-Bak: Part of this research was conducted while the author was at the Max Planck Institute for Informatics, and part of it while he was at the Institute for Theoretical Studies, ETH Zürich. Publisher Copyright: © Karl Bringmann, Sndor Kisfaludi-Bak, Marvin Knnemann, Dniel Marx, and Andr Nusser; licensed under Creative Commons License CC-BY 4.0
Keywords
Dynamic Time Warping, Sequence Similarity Measures
Other note
Citation
Bringmann, K, Kisfaludi-Bak, S, Künnemann, M, Marx, D & Nusser, A 2022, Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves . in X Goaoc & M Kerber (eds), 38th International Symposium on Computational Geometry, SoCG 2022 ., 20, Leibniz International Proceedings in Informatics, LIPIcs, vol. 224, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 1-17, International Symposium on Computational Geometry, Berlin, Berlin, Germany, 07/06/2022 . https://doi.org/10.4230/LIPIcs.SoCG.2022.20