License:
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2022.90
URN: urn:nbn:de:0030-drops-170281
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17028/
Xi, Zoe ;
Kuszmaul, William
Approximating Dynamic Time Warping Distance Between Run-Length 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 dynamic-programming 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 run-length encoding. A natural question is whether the DTW-distance 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 near-quadratic Õ(k?)-time algorithm might exist.
We show that, if a small approximation loss is permitted, then a near-quadratic 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 Run-Length Encoded Strings}},
booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)},
pages = {90:1--90:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-247-1},
ISSN = {1868-8969},
year = {2022},
volume = {244},
editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17028},
URN = {urn:nbn:de:0030-drops-170281},
doi = {10.4230/LIPIcs.ESA.2022.90},
annote = {Keywords: Dynamic time warping distance, approximation algorithms, run-length encodings, computational geometry}
}
Keywords: |
|
Dynamic time warping distance, approximation algorithms, run-length encodings, computational geometry |
Collection: |
|
30th Annual European Symposium on Algorithms (ESA 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
01.09.2022 |