On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric

Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, Bernhard SeegerMFCS 2023 · DOI

TL;DR

This paper investigates the computational complexity of finding a "median" time series that minimizes the total distance to a set of input time series, using the Move-Split-Merge (MSM) distance metric. The authors prove that this problem is NP-hard and W[1]-hard, meaning it's unlikely to have efficient exact solutions, even for simplified cases. However, they also provide a parameterized algorithm that can efficiently find a median when the total distance to the input series is small.

What Problem Does This Paper Address?

In many data analysis tasks, such as classification and clustering, we need to find a representative or "consensus" time series from a collection of similar time series. This representative is often called a median, and its quality depends heavily on the distance metric used. Elastic distance measures, like Dynamic Time Warping (DTW), are popular because they can align time series of different lengths and are robust to temporal shifts. The Move-Split-Merge (MSM) metric is another such measure, known for its effectiveness in classification and its metric properties.

While algorithms exist for computing DTW-based medians, the complexity of finding MSM medians was less understood. This paper aims to fill that gap by analyzing the computational difficulty of the MSM-MEDIAN problem and developing efficient algorithms for specific scenarios.

Methods

The paper's core contributions lie in its theoretical analysis of the MSM-MEDIAN problem's complexity and the development of parameterized algorithms.

  • Hardness Proofs: The authors establish the NP-hardness and W[1]-hardness of MSM-MEDIAN by reducing it from the BINARY CIRCULAR CONSENSUS STRING problem. This reduction is quite intricate, involving the construction of specific time series and transformations that mirror the structure of the original string problem. They show these hardness results hold even when the input time series have only three distinct values.
  • Parameterized Algorithm: For the case where the total distance of the median to the input time series is bounded, the authors present a parameterized algorithm. This algorithm leverages a dynamic programming approach, but crucially, it prunes the search space based on the cost bound. This allows for efficient computation when the "median-ness" is high, even if the number of input time series is large.

Datasets

Not discussed in the paper. The paper focuses on theoretical complexity and algorithmic design rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • MSM-MEDIAN is Hard: The NP-hardness and W[1]-hardness results are significant because they imply that finding an exact MSM median is computationally expensive in the general case. This justifies the search for approximation algorithms or parameterized solutions.
  • The Power of Bounded Distance: The parameterized algorithm highlights that MSM-MEDIAN becomes tractable when the desired median is "close" to the input time series. This is a common theme in parameterized complexity, where problems become easier when a specific parameter (here, the total distance) is small.
  • Reduction from String Problems: The successful reduction from a string problem to a time series problem demonstrates a powerful technique for proving hardness in this domain. It suggests that insights from string algorithms might be transferable to time series analysis.

Key Results

  • NP-hard and W[1]-hard: The MSM-MEDIAN problem is proven to be NP-hard and W[1]-hard with respect to the number of input time series ($k$). This holds even for time series with only three distinct values.
  • Parameterized Algorithm: An algorithm is presented that solves MSM-MEDIAN in $2^{O(d/c)} \cdot |I|^{O(1)}$ time, where $d$ is the total distance of the median to the input time series and $c$ is the cost of split/merge operations. This means that if the median is "good" (small $d$), the problem can be solved efficiently.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on complexity and algorithm design. Empirical evaluation of the proposed algorithms on real-world datasets would be a valuable next step.
  • Parameter $d/c$: While the parameterized algorithm is efficient for small $d/c$, the exponential dependence on this parameter can still be prohibitive if $d/c$ is large. Future work could explore ways to improve this dependency or develop better approximation algorithms.
  • Specific MSM Properties: The paper leverages specific properties of the MSM metric and its transformation graphs. Further research could explore how these properties can be exploited for other MSM-related problems.

Summary updated

BibTeX
@inproceedings{holznigenkemper2023complexity,
  author = {Jana Holznigenkemper and Christian Komusiewicz and Nils Morawietz and Bernhard Seeger},
  title = {{On the Complexity of Computing Time Series Medians Under the Move-Split-Merge Metric}},
  booktitle = {MFCS},
  year = {2023},
  doi = {10.4230/lipics.mfcs.2023.54},
}
Figure