Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets

By Chin-Chia Michael Yeh, Yan Zhu, Liudmila Ulanova, Nurjahan Begum, Yifei Ding, Hoang Anh Dau, Diego Furtado Silva, Abdullah Mueen, Eamonn J. Keogh. Industrial Conference on Data Mining, 2016

689 citations recorded by the source corpus.

The all-pairs-similarity-search (or similarity join) problem has been extensively studied for text and a handful of other datatypes. However, surprisingly little progress has been made on similarity joins for time series subsequences. The lack of progress probably stems from the daunting nature of the problem. For even modest sized datasets the obvious nested-loop algorithm can take months, and the typical speed-up techniques in this domain (i.e., indexing, lower-bounding, triangular-inequality pruning and early abandoning) at best produce one or two orders of magnitude speedup. In this work we introduce a novel scalable algorithm for time series subsequence all-pairs-similarity-search. For exceptionally large datasets, the algorithm can be trivially cast as an anytime algorithm and produce high-quality approximate solutions in reasonable time. The exact similarity join algorithm computes the answer to the time series motif and time series discord problem as a side-effect, and our algorithm incidentally provides the fastest known algorithm for both these extensively-studied problems. We demonstrate the utility of our ideas for two time series data mining problems, including motif discovery and novelty discovery.

Subfields: Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/a68271101067d91412bec50d71e1191c9be679fb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Anomaly Detection in Time Series: A Comprehensive Evaluation (2022, methodology): “Representatives of this category in our evaluation are: CBLOF [59], COF [130], DBStream [55], HOT SAX [70], Hybrid KNN [124], k-Means [151], KNN [110], LOF [22], NormA-SJ [15], PhaseSpaceSVM (PS-SVM) [85], SAND [17], SSA [155], STAMP [156], STOMP [164], Sub-LOF [22], VALMOD [82], and Left STAMPi [15”
DCdetector: Dual Attention Contrastive Representation Learning for Time Series Anomaly Detection (2023, result): “We also compare our model with a time-series subsequence anomaly detection algorithm Matrix Profile [83].”
Spatio-Temporal Data Mining (2017, methodology): “Recently, the development of efficient approaches for constructing ‘matrix profile’ [Yeh et al. 2016], a vector comprised of minimum non-trivial distance for each subsequence in time series A with subsequences in time seies B, have enabled an efficient approach for motif discovery [Zhu et al. 2016].”
Deep Learning for Time Series Anomaly Detection: A Survey (2022, neutral): “The most meaningful deviations are usually those that are significantly different from the norm.”
Tslearn, A Machine Learning Toolkit for Time Series Data (2020, methodology): “…provides standard statistical models for time series analysis, hmmlearn 3 that focuses on Hidden Markov Models, stumpy (Law, 2019) that relies on the matrix proﬁle data structure (Yeh et al., 2016), or pyflux (Taylor, 2016), which oﬀers a large panel of probabilistic models aimed at forecasting.”
Current Time Series Anomaly Detection Benchmarks are Flawed and are Creating the Illusion of Progress (2020, background): “However, in the last five years there has been an explosion of interest in this topic, with at least one or two papers on the topic appearing each year in virtually every database, data mining and machine learning conference, including SIGKDD [2], [3], ICDM [4], ICDE, SIGMOD, VLDB, etc.”
TranAD: Deep Transformer Networks for Anomaly Detection in Multivariate Time Series Data (2022, background): “Time-series discord discovery is another recently proposedmethod for fault prediction [16, 37, 58, 59].”