2026-08-10T23:44:13Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17028 2024-03-06T10:59:00Z ddc:004 open_access

Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings Xi, Zoe Kuszmaul, William Dynamic time warping distance approximation algorithms run-length encodings computational geometry 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Zoe Xi and William Kuszmaul 2022 Is Part Of LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2022.90 urn:nbn:de:0030-drops-170281 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.90 eng https://creativecommons.org/licenses/by/4.0/legalcode