License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2020.28
URN: urn:nbn:de:0030-drops-121538
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12153/
Go to the corresponding LIPIcs Volume Portal

Schaar, Nathan ; Froese, Vincent ; Niedermeier, Rolf

Faster Binary Mean Computation Under Dynamic Time Warping

pdf-format:
LIPIcs-CPM-2020-28.pdf (0.7 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{schaar_et_al:LIPIcs:2020:12153,
  author =	{Nathan Schaar and Vincent Froese and Rolf Niedermeier},
  title =	{{Faster Binary Mean Computation Under Dynamic Time Warping}},
  booktitle =	{31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)},
  pages =	{28:1--28:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-149-8},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{161},
  editor =	{Inge Li G{\o}rtz and Oren Weimann},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12153},
  URN =		{urn:nbn:de:0030-drops-121538},
  doi =		{10.4230/LIPIcs.CPM.2020.28},
  annote =	{Keywords: consensus string problems, time series averaging, minimum 1-separated sum, sparse strings}
}

Keywords: consensus string problems, time series averaging, minimum 1-separated sum, sparse strings
Collection: 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Issue Date: 2020
Date of publication: 09.06.2020
Supplementary Material: Python source code available at https://www.akt.tu-berlin.de/menue/software/.

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI