Photo by Amos Nachoum

The UCR Matrix Profile Page

Funded by NSF  IIS 1161997 II, IIS 1510741, CNS 1544969
"(for an industrial IoT problem) Matrix Profiles perform well with almost no parameterisation needed." Anton et al ICDM 2018.
"While there will never be a mathematical silver bullet, we have discovered that the Matrix Profile, a novel algorithm developed by the Keogh research group at UC-Riverside, is a powerful tool." (full post). Andrew Van Benschoten, lead engineer at Target.


The Matrix Profile (and the algorithms to compute it: STAMP, STAMPI, STOMP, SCRIMP, SCRIMP++  and GPU-STOMP), has the potential to revolutionize time series data mining because of its generality, versatility, simplicity and scalability.  In particular it has implications for time series motif discovery, time series joins, shapelet discovery (classification), density estimation, semantic segmentation, visualization, rule discovery, clustering etc (note, for pure similarity search, we suggest you see MASS for Euclidean Distance, and the UCR Suite for DTW)

Our overarching claim has three parts:

1) Given only the Matrix Profile, most time series data mining tasks are trivial.
2) The Matrix Profile can be computed very efficiently.
3) Algorithms that are built on top the Matrix Profile inherit all its desirable properties. For example, we can use the Matrix Profile to find time series motifs. Because the Matrix Profile can be incrementally computed, we have the first incremental time series motif discovery algorithm. Because the Matrix Profile can be computed in an anytime fashion, we have the first anytime time series motif discovery algorithm. Because the Matrix Profile can leverage GPUs, we have..
 
The advantages of using the Matrix Profile (over hashing, indexing, brute forcing a dimensionality reduced representation etc.) for most time series data mining tasks include:

  1. It is exact: For motif discovery, discord discovery, time series joins etc., the Matrix Profile based methods provide no false positives or false dismissals.
  2. It is simple and parameter-free: In contrast, the more general spatial access method algorithms typically require building and tuning spatial access methods and/or hash function.
  3. It is space efficient: Matrix Profile construction algorithms requires an inconsequential space overhead, just linear in the time series length with a small constant factor, allowing massive datasets to be processed in main memory.
  4. It allows anytime algorithms: While our exact algorithms are extremely scalable, for extremely large datasets we can compute the Matrix Profile in an anytime fashion, allowing ultra-fast approximate solutions.
  5. It is incrementally maintainable: Having computed the Matrix Profile for a dataset, we can incrementally update it very efficiently. In many domains this means we can effectively maintain exact joins/motifs/discords on streaming data forever.
  6. It does not require the user to set similarity/distance thresholds: For time series joins, the Matrix Profile provides full joins, eliminating the need to specify a similarity threshold, which is an unintuitive task for time series.
  7. It can leverage hardware: Matrix Profile construction is embarrassingly parallelizable, both on multicore processors and in distributed systems.
  8. It has time complexity that is constant in subsequence length: This is a very unusual and desirable property; all known time series join/motif/discord algorithms scale poorly as the subsequence length grows. In contrast, we have shown time series joins/motifs with subsequences lengths up to 100,000, at least two orders of magnitude longer than any other work we are aware of.
  9. It can be constructed in deterministic time: All join/motif/discord algorithms we are aware of can radically different times to finish on two (even slightly) different datasets. In contrast, given only the length of the time series, we can precisely predict in advance how long it will take to compute the Matrix Profile
  10. It can handle missing data: Even in the presence of missing data, we can provide answers which are guaranteed to have no false negatives.

Given all these features, the Matrix Profile has implications for many, perhaps most, time series data mining tasks.

Papers:
Tutorials
 

The Matrix Profile Tutorial


Part 1: PPT or PDF
Part 2: PPT or PDF

 MP Tutorial

Code by the Community: Here we list some MP implementations by others. Naturally we neither take credit (or blame) for any of this work.  Python, R, Golang,

Code by UCR Team:  Version 2.0

Please note this code is not STAMP or STOMP, but SCRIMP++ (which appears in Matrix Profile XI), which is as fast as STOMP, but also an anytime algorithm. The code is wrapped inside a simple Matlab GUI (that adds a lot of time overhead), to allow non-specailists to interact with their data. If you are writing a paper, please do not comparing timing results to this version, it would not be fair to us (contact us for the faster, but less user friendly code).

First read this, then download this data (some penguin data) and download the code into your Matlab path:
At the command line, type...

>> load MP_first_test_penguin_sample
>> [matrixProfile, profileIndex, motifIndex, discordIndex] = interactiveMatrixProfileVer2(smooth(penguin_sample,10) ,800);

As you can see from the image below, even though the data has 109,043 datapoints, and the subsequence is high dimensional (800 datapoints), in about a second we have already found some very interesting motifs:
The first is a valley happens during a dive. The third motif, a W shape followed by a long constant, happens when the penguin.   

Happy motif hunting, from the Matrix Profile team.

GUI of Stamp Tool