1 Search Results for "Xi, Zoe"

Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings

Authors: Zoe Xi and William Kuszmaul

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

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).

Cite as

Zoe Xi and William Kuszmaul. Approximating Dynamic Time Warping Distance Between Run-Length Encoded Strings. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 90:1-90:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

  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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.90},
  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}
  • Refine by Author
  • 1 Kuszmaul, William
  • 1 Xi, Zoe

  • Refine by Classification
  • 1 Theory of computation → Approximation algorithms analysis

  • Refine by Keyword
  • 1 Dynamic time warping distance
  • 1 approximation algorithms
  • 1 computational geometry
  • 1 run-length encodings

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback

Feedback for Dagstuhl Publishing

Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail