MOMENTI: Scalable Motif Mining in Multidimensional Time Series

Matteo Ceccarello, Francesco Pio Monaco, Francesco Silvestri

TL;DR

MOMENTI is a scalable algorithm designed to find repeating patterns, or "motifs," in multidimensional time series. By leveraging self-tuning Locality Sensitive Hashing (LSH), it achieves subquadratic time complexity, finding top-$k$ motifs orders of magnitude faster than exact state-of-the-art methods while providing strong probabilistic guarantees on accuracy.

What Problem Does This Paper Address?

Time series data—sequences of measurements over time—are everywhere, from industrial sensors to heart rate monitors. Often, these signals are multidimensional, meaning multiple sensors are recording synchronized data. A key task in analyzing this data is motif mining: finding pairs of subsequences that are nearly identical.

The challenge is twofold:

  1. Subdimensional Motifs: In a 100-dimension system, a meaningful pattern might only appear in 5 specific dimensions, while the other 95 are just noise. Standard methods that look at all dimensions simultaneously often miss these "hidden" patterns.
  2. Scalability: Finding the best motifs traditionally requires comparing every possible pair of subsequences. For a time series of length $n$, this takes $O(n^2)$ time. When you add the search for the right subset of dimensions, the complexity explodes, making it impossible to process large datasets (millions of points) in a reasonable timeframe.

Methods

The authors introduce MOMENTI (MOtifs in MultidimEnsioNal TImeseries), which breaks the quadratic time barrier using Locality Sensitive Hashing (LSH).

Key technical innovations include:

  • Independent Hashing: Instead of hashing entire multidimensional blocks, MOMENTI hashes each dimension independently. A pair of subsequences becomes a "candidate" only if they collide (hash to the same value) in at least $d$ dimensions.
  • Self-Tuning Parameters: LSH usually requires expert tuning of parameters like the number of hash functions ($K$) and repetitions ($L$). MOMENTI automatically estimates these based on the data distribution and user-defined memory limits.
  • Tensoring: To reduce the computational cost of hashing, the algorithm uses a "tensoring" approach that cuts the number of required hash evaluations from $L$ to $\sqrt{L}$.
  • Probabilistic Stopping Condition: The algorithm doesn't just run blindly; it uses a rigorous statistical stopping condition. It stops as soon as it can guarantee, with probability $1-\delta$, that no better motif has been missed.
Figure 1: Multidimensional motifs found in industrial evaporator data. Note how the pattern repeats in the top and bottom signals, but the middle one is irrelevant noise.

Datasets

The authors evaluated MOMENTI on a diverse set of real-world and synthetic datasets:

  • Industrial/Scientific: Evaporator (sensor data), Potentials (skin potentials), Quake (seismic waveforms).
  • Audio/Biological: RUTH (Mel-spectrogram of a song), Whales (underwater acoustic recordings).
  • Human Activity: LTMM (3-day accelerometer data), El_load (household electricity consumption).
  • Synthetic: Random walks with planted motifs to test scalability up to 100 million points.

Key Insights and Ideas

  • Pruning is Power: The core "aha" moment is that you don't need to be exact to be right. By using LSH to group similar items, MOMENTI can ignore the vast majority of subsequence pairs that are clearly not motifs, focusing its heavy lifting only on promising candidates.
  • Anytime Discovery: Because the algorithm processes the most likely candidates first, it has "anytime" properties. A user can stop the search early and still receive the best motifs found so far, along with a calculated error probability.
  • Robustness to Irrelevant Dimensions: The subdimensional formulation is crucial. The experiments showed that even if you add 256 dimensions of pure noise to a dataset, MOMENTI still finds the underlying motif with perfect recall.

Key Results

  • Massive Speedups: On the LTMM dataset (25 million points), the state-of-the-art exact baseline (MSTUMP) would take an estimated 11.8 days. MOMENTI finished in just 15.6 hours.
  • Subquadratic Scaling: While exact methods scale quadratically ($n^2$), MOMENTI demonstrates subquadratic scaling, making it viable for datasets that were previously untouchable.
  • High Fidelity: Despite being a probabilistic algorithm, MOMENTI consistently achieved a Mean Absolute Relative Error (MARE) of less than 3% compared to exact solutions.
  • Memory Efficiency: MOMENTI generally required significantly less memory than its competitors, often by an order of magnitude on larger datasets.

Limitations and Future Work

While MOMENTI is a major step forward, there are areas for further exploration:

  • Distance Measures: The current implementation focuses on z-normalized Euclidean distance. While the authors suggest it can be generalized to other measures (like Dynamic Time Warping), this wasn't the primary focus of the experimental evaluation.
  • Memory vs. Speed Trade-off: Although tensoring helps, LSH indices still require memory proportional to the number of repetitions ($L$). For extremely long time series on memory-constrained hardware, this could still be a bottleneck.
  • Top-k vs. All-Motifs: The algorithm is optimized for finding the best motifs. If a user needs to find every pattern that meets a certain threshold (even weak ones), the pruning might be less effective.

Summary updated

Abstract

Time series play a fundamental role in many domains, capturing a plethora of information about the underlying data-generating processes. When a process generates multiple synchronized signals we are faced with multidimensional time series. In this context a fundamental problem is that of motif mining, where we seek patterns repeating twice with minor variations, spanning some of the dimensions. State of the art exact solutions for this problem run in time quadratic in the length of the input time series. We provide a scalable method to find the top-k motifs in multidimensional time series with probabilistic guarantees on the quality of the results. Our algorithm runs in time subquadratic in the length of the input, and returns the exact solution with probability at least $1-δ$, where $δ$ is a user-defined parameter. The algorithm is designed to be adaptive to the input distribution, self-tuning its parameters while respecting user-defined limits on the memory to use. Our theoretical analysis is complemented by an extensive experimental evaluation, showing that our algorithm is orders of magnitude faster than the state of the art.
BibTeX
@article{ceccarello2025momenti,
  author = {Matteo Ceccarello and Francesco Pio Monaco and Francesco Silvestri},
  title = {{MOMENTI: Scalable Motif Mining in Multidimensional Time Series}},
  journal = {Proc. VLDB Endow.},
  year = {2025},
  doi = {10.14778/3748191.3748208},
}
Figure