Search

Thesis
Peer Reviewed

Exact Primitives for Time Series Data Mining

Mueen, Abdullah Al
Advisor(s): Keogh, Eamonn

UC Riverside Electronic Theses and Dissertations (2012)

Data mining and knowledge discovery algorithms for time series data use primitives such as bursts, periods, motifs, outliers and shapelets as building blocks. For example a model of global temperature considers both bursts (i.e. solar fare) and periods (i.e. sunspot cycle) of the sun. Algorithms for finding these primitives are required to be fast to process large datasets. Because exact algorithms that guarantee the optimum solutions are very slow for their immense computational requirements, existing algorithms find primitives approximately. This thesis presents efficient exact algorithms for two primitives, time series motif and time series shapelet. A time series motif is any repeating segment whose appearances in the time series are too similar to happen at random and thus expected to bear important information about the structure of the data. A time series shapelet is any subsequence that describes a class of time series differentiating from other classes and thus can be used to classify unknown instances.

We extend the primitives for different environments. We show exact methods to find motifs in three different types of time series data. They are the in-memory datasets suitable for batched processing, the massive archives of time series stored in hard drives and finally, the streaming time series with limited storage. We also describe an exact algorithm for logical-shapelet discovery that combines multiple shapelets to better describe complex concepts.

We use efficient bounds to the goodness measures to increase the efficiency of the exact algorithms. The algorithms are orders of magnitude faster than the trivial solutions and successfully discover motifs/shapelets of real time series from diverse sensors such as EEG, ECG, EPG, EOG, Accelerometers and Motion captures. We show applicability of these algorithms as subroutines in high-level data mining tasks such as summarization, classification and compression.

Cover page: Exact Primitives for Time Series Data Mining

Article
Peer Reviewed

Exploiting a novel algorithm and GPUs to break the ten quadrillion pairwise comparisons barrier for time series motifs and joins

UC Riverside Previously Published Works (2018)

Time series motifs are approximately repeated subsequences found within a longer time series. They have been in the literature since 2002, but recently they have begun to receive significant attention in research and industrial communities. This is perhaps due to the growing realization that they implicitly offer solutions to a host of time series problems, including rule discovery, anomaly detection, density estimation, semantic segmentation, summarization, etc. Recent work has improved the scalability so exact motifs can be computed on datasets with up to a million data points in tenable time. However, in some domains, for example seismology or climatology, there is an immediate need to address even larger datasets. In this work, we demonstrate that a combination of a novel algorithm and a high-performance GPU allows us to significantly improve the scalability of motif discovery. We demonstrate the scalability of our ideas by finding the full set of exact motifs on a dataset with one hundred and forty-three million subsequences, which is by far the largest dataset ever mined for time series motifs/joins; it requires ten quadrillion pairwise comparisons. Furthermore, we demonstrate that our algorithm can produce actionable insights into seismology and ethology.

Cover page: Exploiting a novel algorithm and GPUs to break the ten quadrillion pairwise comparisons barrier for time series motifs and joins

Article
Peer Reviewed

Super‐Efficient Cross‐Correlation (SEC‐C): A Fast Matched Filtering Code Suitable for Desktop Computers

UC Riverside Previously Published Works (2019)

Article
Peer Reviewed

Matrix Profile II: Exploiting a Novel Algorithm and GPUs to Break the One Hundred Million Barrier for Time Series Motifs and Joins

UC Riverside Previously Published Works (2016)

Time series motifs have been in the literature for about fifteen years, but have only recently begun to receive significant attention in the research community. This is perhaps due to the growing realization that they implicitly offer solutions to a host of time series problems, including rule discovery, anomaly detection, density estimation, semantic segmentation, etc. Recent work has improved the scalability to the point where exact motifs can be computed on datasets with up to a million data points in tenable time. However, in some domains, for example seismology, there is an insatiable need to address even larger datasets. In this work we show that a combination of a novel algorithm and a high-performance GPU allows us to significantly improve the scalability of motif discovery. We demonstrate the scalability of our ideas by finding the full set of exact motifs on a dataset with one hundred million subsequences, by far the largest dataset ever mined for time series motifs. Furthermore, we demonstrate that our algorithm can produce actionable insights in seismology and other domains.

Article
Peer Reviewed

The Swiss army knife of time series data mining: ten useful things you can do with the matrix profile and ten lines of code

UC Riverside Previously Published Works (2020)