Xi, Zoe ;
Kuszmaul, William
Approximating Dynamic Time Warping Distance Between RunLength Encoded Strings
Abstract
Dynamic Time Warping (DTW) is a widely used similarity measure for comparing strings that encode time series data, with applications to areas including bioinformatics, signature verification, and speech recognition. The standard dynamicprogramming algorithm for DTW takes O(n²) time, and there are conditional lower bounds showing that no algorithm can do substantially better.
In many applications, however, the strings x and y may contain long runs of repeated letters, meaning that they can be compressed using runlength encoding. A natural question is whether the DTWdistance between these compressed strings can be computed efficiently in terms of the lengths k and 𝓁 of the compressed strings. Recent work has shown how to achieve O(k𝓁² + 𝓁 k²) time, leaving open the question of whether a nearquadratic Õ(k𝓁)time algorithm might exist.
We show that, if a small approximation loss is permitted, then a nearquadratic time algorithm is indeed possible: our algorithm computes a (1 + ε)approximation for DTW(x, y) in Õ(k𝓁 / ε³) time, where k and 𝓁 are the number of runs in x and y. Our algorithm allows for DTW to be computed over any metric space (Σ, δ) in which distances are O(log n)bit integers. Surprisingly, the algorithm also works even if δ does not induce a metric space on Σ (e.g., δ need not satisfy the triangle inequality).
BibTeX  Entry
@InProceedings{xi_et_al:LIPIcs.ESA.2022.90,
author = {Xi, Zoe and Kuszmaul, William},
title = {{Approximating Dynamic Time Warping Distance Between RunLength Encoded Strings}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {90:190:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772471},
ISSN = {18688969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17028},
URN = {urn:nbn:de:0030drops170281},
doi = {10.4230/LIPIcs.ESA.2022.90},
annote = {Keywords: Dynamic time warping distance, approximation algorithms, runlength encodings, computational geometry}
}
01.09.2022
Keywords: 

Dynamic time warping distance, approximation algorithms, runlength encodings, computational geometry 
Seminar: 

30th Annual European Symposium on Algorithms (ESA 2022)

Issue date: 

2022 
Date of publication: 

01.09.2022 