Searching and Mining Trillions of Time Series Subsequences under Dynamic Time Warping

By Thanawin Rakthanmanon, Bilson J. L. Campana, Abdullah Mueen, Gustavo E. A. P. A. Batista, M. Brandon Westover, Qiang Zhu, Jesin Zakaria, Eamonn J. Keogh. Knowledge Discovery and Data Mining, 2012

1,125 citations recorded by the source corpus.

Most time series data mining algorithms use similarity search as a core subroutine, and thus the time taken for similarity search is the bottleneck for virtually all time series data mining algorithms. The difficulty of scaling search to large datasets largely explains why most academic work on time series data mining has plateaued at considering a few millions of time series objects, while much of industry and science sits on billions of time series objects waiting to be explored. In this work we show that by using a combination of four novel ideas we can search and mine truly massive time series for the first time. We demonstrate the following extremely unintuitive fact; in large datasets we can exactly search under DTW much more quickly than the current state-of-the-art Euclidean distance search algorithms. We demonstrate our work on the largest set of time series experiments ever attempted. In particular, the largest dataset we consider is larger than the combined size of all of the time series datasets considered in all data mining papers ever published. We show that our ideas allow us to solve higher-level time series data mining problem such as motif discovery and clustering at scales that would otherwise be untenable. In addition to mining massive datasets, we will show that our ideas also have implications for real-time monitoring of data streams, allowing us to handle much faster arrival rates and/or use cheaper and lower powered devices than are currently possible.

Subfields: Signal Processing

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

How researchers see this paper

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

In Signal Processing

Citations in the corpus

Matrix Profile I: All Pairs Similarity Joins for Time Series: A Unifying View That Includes Motifs, Discords and Shapelets (2016, methodology): “To modify the current algorithm to compute the self-similarity join matrix profile of a time series TA, we simply replace TB in line 1 with TA, replace B with A in line 4, and ignore trivial match in D when performing ElementWiseMin in line 5.”
Toeplitz Inverse Covariance-Based Clustering of Multivariate Time Series Data (2017, methodology): “Methods include several variations of dynamic time warping [3, 23, 25, 39], symbolic representations [29, 30], and rule-based motif discovery [11, 28].”
k-Shape: Efficient and Accurate Clustering of Time Series (2016, methodology): “However, as DTW is more appropriate for many time-series tasks [37, 55], several methods have been proposed to average timeseries sequences under DTW.”
Time-series clustering - A decade review (2015, background): “Moreover, there are many on-going research projects aimed to improve the existing techniques [10,11].”
Time Series Classification Using Multi-Channels Deep Convolutional Neural Networks (2014, background): “reach the best performance of classification in most domains [6].”
Classification of time series by shapelet transformation (2013, background): “Further speed improvements, proposed in Rakthanmanon et al. (2012), can be achieved by normal-ising subsequences during the distance calculation, and by reordering the candidate S to compare the largest values ﬁrst.”
Highly Comparative Feature-Based Time-Series Classification (2014, methodology): “using lower bounds [1], [5], [35], and speedups can be obtained using indexing [36], [37], [38] or time-domain dimensionality reduction [39], the need to calculate many distances between pairs of time series is fundamental to”
Exploiting multi-channels deep convolutional neural networks for multivariate time series classification (2015, background): “In the literature, DTW is considered as an alternative that is more robust than Euclidean distance and can align two sequences effectively [2, 9, 10].”
Multi-Scale Convolutional Neural Networks for Time Series Classification (2016, methodology): “We also select 11 existing methods with state-of-the-art results published within the recent three years, including: DTW with a warping window constraint set through cross validation (DTW CV) [23], Fast Shapelet (FS) [24] , SAX with vector space model (SV) [29], Bag-of-SFA-Symbols (BOSS) [26], Shotg”
Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015, background): “There are a number of publications detailing data mining techniques to search, classify, and cluster enormous amounts of time series data eﬃciently [8, 23, 24].”
TSclust: An R Package for Time Series Clustering (2014, background): “In fact, conventional metrics like Minkowski, DTW or Fr´echet distances may lead to common mis-understandings if the time series are not previously normalized (see illustrative examples in Rakthanmanon et al. 2012).”
k-Shape: Efficient and Accurate Clustering of Time Series (2015, methodology): “Several optimizations have been proposed to further speed up cDTW [65].”
Learning-Based Methods for Comparing Sequences, with Applications to Audio-to-MIDI Alignment and Matching (2016, methodology): “(Rakthanmanon et al., 2012) provides a thorough overview of these techniques and shows that for some problems they can allow exact search of databases with trillions of data points.”
Minimum redundancy maximum relevance feature selection approach for temporal gene expression data (2017, methodology): “2) which is often used as a preprocessing step to DTW [17–19]: where g i , p is a time series corresponding to i th gene and p th observation (patient), and ¯ g i , p and σ i , p are the average value and standard deviation of this time series.”