Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings

Itai Boneh; Shay Golan; Shay Mozes; Oren Weimann

paper

Near-Optimal Dynamic Time Warping on Run-Length Encoded Strings

arXiv:2302.06252

Abstract

We give an $O ~ (n^{2})$ time algorithm for computing the exact Dynamic Time Warping distance between two strings whose run-length encoding is of size at most $n$ . This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest $O (n^{3})$ time exact algorithm and the $O ~ (n^{2})$ time approximation algorithm.