MOMENTI: Scalable Motif Mining in Multidimensional Time Series
This addresses the scalability issue for researchers and practitioners analyzing complex time series data, though it is an incremental improvement over existing methods.
The paper tackles the problem of motif mining in multidimensional time series, which has quadratic time complexity in state-of-the-art exact solutions, and presents a scalable algorithm that runs in subquadratic time with probabilistic guarantees, achieving orders of magnitude faster performance in experiments.
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.