TL;DR
Computing the consensus "mean" string under Dynamic Time Warping (DTW) is NP-hard in general, but solvable in polynomial time for binary strings. This paper introduces tight bounds on the length of an optimal binary mean and leverages connections to integer optimization to slash the worst-case running time to $O(k n^{1.87})$ and $O(k(n + m(m - \mu)))$. In practice, their combinatorial algorithm delivers speedups of several orders of magnitude on real-world sensor data.
What Problem Does This Paper Address?
In time series analysis and string algorithms, finding a consensus string (a "mean" or "center") that represents a collection of $k$ input sequences is a fundamental problem. While Hamming distance is common, it fails when sequences vary in length or exhibit local speed variations. Dynamic Time Warping (DTW) provides a flexible non-linear alignment distance, but finding a mean sequence that minimizes the sum of squared DTW distances is computationally hard:
- For general real-valued time series or ternary strings, DTW-Mean is NP-hard.
- For binary strings, however, exact mean computation is polynomial-time solvable.
Prior work established an $O(k n^3)$ (or straightforwardly $O(k n^2)$) dynamic programming algorithm for binary strings of maximum length $n$. This paper tackles the challenge of computing binary DTW means significantly faster, both theoretically and in practice.
Methods
The paper's approaches rely on several key combinatorial tools:
- Condensation and Block Representation: Repeated identical consecutive symbols can be collapsed into a condensed string (e.g., $001110 \to 010$). A string's condensation length $|\tilde{s}|$ equals its number of alternating 0/1 blocks. An optimal mean can always be found in condensed form.
- Tight Length Bounds: The authors prove that any optimal condensed mean $z$ must satisfy $\mu - 2 \le |\tilde{z}| \le m + 1$, where $\mu$ is the median condensation length and $m$ is the maximum condensation length across all $k$ input strings. This restricts the number of mean candidates to $O(m - \mu)$ instead of $O(n)$.
- Reduction to Min 1-Separated Sum (MSS): Aligning an input string with a shorter condensed candidate reduces to MSS: picking non-consecutive blocks whose deletion minimizes total misaligned block length.
- Using a subquadratic MSS algorithm by Abboud et al., the search runs in $O(k n^{1.87})$ time.
- Using a simpler dynamic program for MSS, the search runs in $O(k(n + m(m - \mu)))$ time.
- Linear-Time Special Cases:
- For $k = 2$ strings, the authors show that a condensed mean is computable in strictly $O(n)$ time.
- For $k = 3$ strings that start and end with the same symbols, an optimal mean length can be found greedily in linear time.
Datasets
The authors evaluated their algorithm using:
- CASAS Smart Home Datasets (HH101–HH130): Real-world time series recording binary sensor events (e.g., doors opening/closing) sampled at 1-minute and 10-minute intervals, providing sparse binary data with sparsities around $0.01$ and $0.1$ (where sparsity is defined as $|\tilde{s}|/|s|$).
- Synthetic Random Binary Strings: Generated across varied lengths ($n$ up to 10,000), number of sequences ($k$ up to 60), and sparsities ranging from dense ($\approx 0.5$) to highly alternating ($1.0$).
Key Insights and Ideas
- The "Median Pivot" Principle: Adding or deleting blocks in candidate means shifts distances up or down based on whether candidate length is above or below input condensation lengths. Because the median balances the number of inputs requiring additions versus deletions, optimal means cannot stray far from the median condensation length $\mu$.
- Asymmetric Distances Are Cheap: Evaluating distances from a longer condensed string to a shorter arbitrary string takes $O(1)$ time via closed-form formulas. Only evaluating candidates shorter than an input string requires solving MSS instances.
- Sparse Data Leads to Massive Speedups: In many applications (like smart home sensors), consecutive states persist for long periods ($m \ll n$). Because the algorithm's non-linear term depends on $m(m - \mu)$ rather than $n^2$, sparse inputs yield virtually linear performance.
Key Results
- Theoretical Bounds: Established algorithms running in $O(k n^{1.87})$ and $O(k(n + m(m - \mu)))$, strictly improving upon the previous $O(k n^2)$ bound.
- Speedups on Real-World Data: On CASAS benchmarks, the fast algorithm ran $\approx 250\times$ faster than standard DP at sparsity $\approx 0.1$, and $\approx 350\times$ faster at sparsity $\approx 0.01$.
- Scaling on Large Inputs: On synthetic data with sparsity $\approx 0.1$, the new algorithm solved instances with $n = 10{,}000$ in half the time that the standard DP baseline took for $n = 1{,}000$.
- Structure of Optimal Means: Empirical testing revealed that for dense data ($\text{sparsity} > 0.5$), the mean length almost never differs from the median condensation length by more than 1. Furthermore, the mean’s starting symbol matched the majority starting symbol of the inputs in $70\%\text{--}97\%$ of tested runs.
Limitations and Future Work
- The $O(kn^{1.87})$ Algorithm in Practice: The theoretically faster $O(k n^{1.87})$ bound relies on an intricate algebraic black-box algorithm for MSS that remains unimplemented and is likely slower in practice due to large constant factors.
- Arbitrary $k=3$ Inputs: While $k=2$ is fully solved in linear time, the linear-time algorithm for $k=3$ requires matching boundary symbols; resolving unrestricted 3-string inputs in linear time remains a conjecture.
- Open Complexity for Fixed $k$: The authors pose whether Binary DTW-Mean can be solved in linear time for every constant $k$ (i.e., fixed-parameter tractable in $O(f(k) \cdot n)$ time), and suggest extending similar speedups to weighted and center-string ("Closest String") variants.
Summary updated