@inproceedings{641181d5adac43b9920f4500c01e4cbb,
title = "{\~O}ptimal Dynamic Time Warping on Run-Length Encoded Strings",
abstract = "Dynamic Time Warping (DTW) distance is the optimal cost of matching two strings when extending runs of letters is for free. Therefore, it is natural to measure the time complexity of DTW in terms of the number of runs n (rather than the string lengths N). In this paper, we give an {\~O}(n2) time algorithm for computing the DTW distance. This matches (up to log factors) the known (conditional) lower bound, and should be compared with the previous fastest O(n3) time exact algorithm and the {\~O}(n2) time approximation algorithm. Our method also immediately implies an {\~O}(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n2k) and O(Nk) time exact algorithms and the {\~O}(nk) time approximation algorithm.",
keywords = "Dynamic time warping, Fr{\'e}chet distance, edit distance, run-length encoding",
author = "Itai Boneh and Shay Golan and Shay Mozes and Oren Weimann",
note = "Publisher Copyright: {\textcopyright} Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann.; 51st International Colloquium on Automata, Languages, and Programming, ICALP 2024 ; Conference date: 08-07-2024 Through 12-07-2024",
year = "2024",
month = jul,
doi = "10.4230/LIPIcs.ICALP.2024.30",
language = "אנגלית",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Karl Bringmann and Martin Grohe and Gabriele Puppis and Ola Svensson",
booktitle = "51st International Colloquium on Automata, Languages, and Programming, ICALP 2024",
address = "גרמניה",
}