2026-07-23T04:26:42Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12153 2024-03-06T10:49:26Z ddc:004 open_access

Faster Binary Mean Computation Under Dynamic Time Warping Schaar, Nathan Froese, Vincent Niedermeier, Rolf consensus string problems time series averaging minimum 1-separated sum sparse strings Many consensus string problems are based on Hamming distance. We replace Hamming distance by the more flexible (e.g., easily coping with different input string lengths) dynamic time warping distance, best known from applications in time series mining. Doing so, we study the problem of finding a mean string that minimizes the sum of (squared) dynamic time warping distances to a given set of input strings. While this problem is known to be NP-hard (even for strings over a three-element alphabet), we address the binary alphabet case which is known to be polynomial-time solvable. We significantly improve on a previously known algorithm in terms of worst-case running time. Moreover, we also show the practical usefulness of one of our algorithms in experiments with real-world and synthetic data. Finally, we identify special cases solvable in linear time (e.g., finding a mean of only two binary input strings) and report some empirical findings concerning combinatorial properties of optimal means. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Nathan Schaar and Vincent Froese and Rolf Niedermeier 2020 Is Part Of LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CPM.2020.28 urn:nbn:de:0030-drops-121538 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.28 eng https://creativecommons.org/licenses/by/3.0/legalcode