Faster Binary Mean Computation Under Dynamic Time Warping

Nathan Schaar, Vincent Froese, Rolf Niedermeier

Introduction

In the field of data mining and "stringology," finding a consensus string—a single sequence that best represents a group of input strings—is a fundamental task. While the Hamming distance is a traditional metric, it fails when sequences have different lengths or out-of-sync patterns. Dynamic Time Warping (DTW) has become the preferred alternative because it "warps" time to align sequences, making it essential for speech recognition and sensor data analysis.

However, finding the mean string under DTW (the DTW-Mean problem) is computationally expensive. It is NP-hard for any alphabet with three or more symbols. While the binary case (0s and 1s) is solvable in polynomial time, existing algorithms ($O(kn^3)$) were often too slow for large-scale real-world data. This research bridges the gap between theoretical solvability and practical efficiency by introducing a significantly faster algorithm.

Methodology

The authors leverage the concept of string condensation, where consecutive identical characters are collapsed into one (e.g., 001110 becomes 010). The number of blocks in this condensed version defines the "condensation length."

An illustration of a Dynamic Time Warping (DTW) alignment path between two binary sequences. The grid represents the cost matrix, and the black line indicates the optimal warping path.

Structural Insights

The core technical contribution is a structural lemma proving that the condensation length of an optimal mean string is bounded by the median condensation length of the input strings. This "Median Anchor" drastically narrows the search space compared to previous methods that searched up to length $n+1$.

Algorithmic Refinement

The paper reduces the problem to the "Min 1-Separated Sum" (MSS) problem and proposes two approaches:

  1. A Theoretical Algorithm: Achieving $O(kn^{1.87})$ time.
  2. A Practical Combinatorial Algorithm: Running in $O(k(n + m(m - \mu)))$ time, where $\mu$ is the median condensation length. This version is particularly effective on "sparse" strings—sequences that don't change values frequently, such as binary sensor states.

Key Results

The authors evaluated their practical algorithm using CASAS human activity datasets (binary sensor events) and synthetic data.

  • Massive Speedups: In experiments on sparse real-world data, the new algorithm outperformed standard dynamic programming by factors of 250x to 350x.
  • Scalability: While standard algorithms struggle as input size ($n$) increases, the authors' algorithm remains nearly flat, making it viable for sequences with thousands of elements.
  • Structural Verification: Empirical tests confirmed that for dense data, the mean length is almost always within $\pm 1$ of the median condensation length.

Conclusion and Future Work

By focusing strictly on binary alphabets, the authors demonstrate that the DTW-Mean problem transitions from intractable to highly efficient when combinatorial properties of bit-blocks are exploited. While the speedups are specific to binary data, they provide a major boost for processing sensor signals and other binary time series.

Future research may investigate whether the problem can be solved in linear time for a constant number of strings ($k$), which would represent a significant theoretical milestone. Additionally, extending these structural insights to larger alphabets remains a challenge due to the underlying NP-hardness of those cases.

Summary updated

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
@inproceedings{schaar2020faster,
  author = {Nathan Schaar and Vincent Froese and Rolf Niedermeier},
  title = {{Faster Binary Mean Computation Under Dynamic Time Warping}},
  booktitle = {CPM},
  year = {2020},
  url = {https://openreview.net/forum?id=ZDNwtGNXgAS},
}
Figure