A symbolic representation of time series, with implications for streaming algorithms

By Jessica Lin, Eamonn J. Keogh, Stefano Lonardi, Bill Yuan-chi Chiu. Workshop on Research Issues on Data Mining and Knowledge Discovery, 2003

2,169 citations recorded by the source corpus.

The parallel explosions of interest in streaming data, and data mining of time series have had surprisingly little intersection. This is in spite of the fact that time series data are typically streaming data. The main reason for this apparent paradox is the fact that the vast majority of work on streaming data explicitly assumes that the data is discrete, whereas the vast majority of time series data is real valued.Many researchers have also considered transforming real valued time series into symbolic representations, nothing that such representations would potentially allow researchers to avail of the wealth of data structures and algorithms from the text processing and bioinformatics communities, in addition to allowing formerly "batch-only" problems to be tackled by the streaming community. While many symbolic representations of time series have been introduced over the past decades, they all suffer from three fatal flaws. Firstly, the dimensionality of the symbolic representation is the same as the original data, and virtually all data mining algorithms scale poorly with dimensionality. Secondly, although distance measures can be defined on the symbolic approaches, these distance measures have little correlation with distance measures defined on the original time series. Finally, most of these symbolic approaches require one to have access to all the data, before creating the symbolic representation. This last feature explicitly thwarts efforts to use the representations with streaming algorithms.In this work we introduce a new symbolic representation of time series. Our representation is unique in that it allows dimensionality/numerosity reduction, and it also allows distance measures to be defined on the symbolic approach that lower bound corresponding distance measures defined on the original series. As we shall demonstrate, this latter feature is particularly exciting because it allows one to run certain data mining algorithms on the efficiently manipulated symbolic representation, while producing identical results to the algorithms that operate on the original data. Finally, our representation allows the real valued data to be converted in a streaming fashion, with only an infinitesimal time and space overhead.We will demonstrate the utility of our representation on the classic data mining tasks of clustering, classification, query by content and anomaly detection.

Subfields: Economics and Econometrics, Signal Processing

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

How researchers see this paper

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

In Economics and Econometrics

In Signal Processing

Citations in the corpus

Preprocessing techniques for context recognition from accelerometer data (2010, methodology): “A recently developed techniques called symbolic aggregate approximation (SAX) uses a piecewise aggregate approximation (PAA) [31] which relies on a gaussian equiprobable distribution function to map range values into string symbols.”
Time-series data mining (2012, methodology): “Many models have already been extended to control data streams, such as clustering [Domingos and Hulten 2000], classi.cation [Hulten et al. 2001], segmentation [Keogh et al. 2003a], or anomaly detection [Chuah and Fu 2007].”
Internet attack knowledge discovery via clusters and cliques of attack traces (2006, methodology): “The method is based on the notion of so called ‘time signature’ of the clusters, introduced in [17] and obtained using a recent time series analysis method called the Symbolic Aggregate approximation (SAX).”
Evaluating Real-Time Anomaly Detection Algorithms -- The Numenta Anomaly Benchmark (2015, background): “It is our hope that eventually a wide assortment of algorithms will be independently evaluated and results reported in a manner that is objectively comparable.”
Towards parameter-free data mining (2004, neutral): “[25].”
Social big data: Recent achievements and new challenges (2015, background): “[84] , a new symbolic representation of time series is proposed that allows for a dimensionality/numerosity reduction.”
k-Nearest Neighbour Classifiers - A Tutorial (2020, background): “• Symbolic Aggregate Approximation (SAX): The idea with SAX is to discretize the time series so that it can be represented as a sequence of symbols [31].”
Mining data streams: a review (2005, background): “[42] have proposed the use of symbolic representation of time series data streams.”
Pattern graph tracking-based stock price prediction using big data (2018, methodology): “For this, we use a prediction accuracy measure that combines Symbolic Aggregate approXi-mation (SAX) [36] and Jaro-Winkler distance [47].”
LSTM-Based EEG Classification in Motor Imagery Tasks (2018, background): “aggregate approximation (SAX) [30], the first symbolic representation of time series that allows for dimension reduction and indexing using a lower-bounding distance measure.”
Graph based anomaly detection and description: a survey (2014, methodology): “We also include other discretization techniques that could apply under this setting such as SAX [Lin et al., 2003], MDL-binning [Kontkanen and Myllymki, 2007], and minimum entropy discretization [Fayyad and Irani, 1993].”
Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015, methodology): “We also identiﬁed lossy time series approximation techniques used in data mining to make the problem set more easily ﬁt within memory [15, 11], but Gorilla is focused on keeping the full resolution representation of data.”
Distributed Analytics and Edge Intelligence: Pervasive Health Monitoring at the Era of Fog Computing (2015, background): “However, the direct application of existing time series mining algorithms, such as [18], will yield unsatis(cid:12)ed results, due to the unique characteristics of sensor data from smartphones.”
Clustering of Electricity Consumption Behavior Dynamics Toward Big Data Applications (2016, methodology): “SAX is a powerful technique for the dimensional reduction and representation of time series data with lower bounding of the Euclidean distance [30].”
HOT SAX: efficiently finding the most unusual time series subsequence (2005, methodology): “APPROXIMATIONS TO MAGIC Before we introduce our techniques for approximating the perfect ordering returned by the hypothetical Magic heuristics, we must briefly review the Symbolic Aggregate ApproXimation (SAX) representation of time series introduced in [10].”
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].”