文章基本信息

标题：Faster Binary Mean Computation Under Dynamic Time Warping
本地全文：下载
作者：Nathan Schaar ; Vincent Froese ; Rolf Niedermeier 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：161
页码：28:1-28:13
DOI：10.4230/LIPIcs.CPM.2020.28
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：consensus string problems; time series averaging; minimum 1-separated sum; sparse strings