2026-08-10T10:48:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20173 2024-07-02T07:52:49Z ddc:004 open_access

Õptimal Dynamic Time Warping on Run-Length Encoded Strings Boneh, Itai Golan, Shay Mozes, Shay Weimann, Oren Dynamic time warping Fréchet distance edit distance run-length encoding 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 Õ(n²) 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(n³) time exact algorithm and the Õ(n²) time approximation algorithm. Our method also immediately implies an Õ(nk) time algorithm when the distance is bounded by k. This should be compared with the previous fastest O(n²k) and O(Nk) time exact algorithms and the Õ(nk) time approximation algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Itai Boneh and Shay Golan and Shay Mozes and Oren Weimann 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.30 urn:nbn:de:0030-drops-201730 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.30 eng https://creativecommons.org/licenses/by/4.0/legalcode