Probabilistic discovery of time series motifs

By Bill Yuan-chi Chiu, Eamonn J. Keogh, Stefano Lonardi. Knowledge Discovery and Data Mining, 2003

667 citations recorded by the source corpus.

Several important time series data mining problems reduce to the core task of finding approximately repeated subsequences in a longer time series. In an earlier work, we formalized the idea of approximately repeated subsequences by introducing the notion of time series motifs. Two limitations of this work were the poor scalability of the motif discovery algorithm, and the inability to discover motifs in the presence of noise.Here we address these limitations by introducing a novel algorithm inspired by recent advances in the problem of pattern discovery in biosequences. Our algorithm is probabilistic in nature, but as we show empirically and theoretically, it can find time series motifs with very high probability even in the presence of noise or "don't care" symbols. Not only is the algorithm fast, but it is an anytime algorithm, producing likely candidate motifs almost immediately, and gradually improving the quality of results over time.

Subfields: Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/8f4ccadd3af8dded2ee6339e66498d1dc5c7ec36

How researchers see this paper

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

In Information Systems

In Signal Processing

Citations in the corpus

Keeping it Short and Simple: Summarising Complex Event Sequences with Multivariate Patterns (2015, neutral): “These patterns are often called ‘motifs’ [12, 6].”
Time series shapelets: a novel technique that allows accurate, interpretable and fast classification (2010, background): “Our work may also be seen as a form of a supervised motif discovery algorithm (Chiu et al. 2003), in that we are looking for repeated patterns (as in motif discovery).”
Making Time-Series Classification More Accurate Using Learned Constraints (2004, background): “The measurement of similarity between two time series is an important subroutine in many data mining applications, including rule discovery [12], clustering [1] [14], anomaly detection [13], motif discovery [8], and classification [15][22].”
HOT SAX: efficiently finding the most unusual time series subsequence (2005, methodology): “Such matches have previously been called trivial matches [2].”
A review on time series data mining (2011, methodology): “are also called motif discovery (Chiu et al., 2003; Tanaka et al., 2005) and anomaly detection (Chan and Mahoney, 2005; Wei”
Time-series clustering - A decade review (2015, background): “This task itself, fall into two categories: The first group is the one which is used to find patterns that frequently appears in the dataset [29,30].”
Experiencing SAX: a novel symbolic representation of time series (2007, methodology): “We carefully reimplemented the random projection algorithm of Tompa and Buhler, making minor changes in the post-processing step to allow for the fact that although we are hashing random projections of our symbolic representation, we actually wish to discover motifs defined on the original raw data ”
Time series shapelets: a new primitive for data mining (2009, background): “Our work may also be seen as a form of a supervised motif discovery algorithm [3].”
A combined pose, object, and feature model for action understanding (2012, methodology): “[26, 25, 21, 10, 27, 32, 4, 2]), recent successful methods have relied upon visual features to perform action classification (e.”
Spatio-Temporal Data Mining (2017, background): “While the naïve approach for discovering motifs is quadratic in the length of the time series, approximate approaches [Chiu et al. 2003; Meng et al. 2008; Minnen et al. 2007] have also been designed.”