Welcome to the SAX

SAX is the first symbolic representation for time series that allows for dimensionality reduction and indexing with a lower-bounding distance measure. In classic data mining tasks such as clustering, classification, index, etc., SAX is as good as well-known representations such as Discrete Wavelet Transform (DWT) and Discrete Fourier Transform (DFT), while requiring less storage space. In addition, the representation allows researchers to avail of the wealth of data structures and algorithms in bioinformatics or text mining, and also provides solutions to many challenges associated with current data mining tasks. One example is motif discovery, a problem which we defined for time series data. There is great potential for extending and applying the discrete representation on a wide class of data mining tasks.

SAX was invented by Eamonn Keogh and Jessica Lin in 2002 (Jessica came up with the name!). Jessica Lin is now an Assistant Professor at GMU. Her SAX page is here.

Edward Tufte was kind enough to mention that SAX allows a sparkline like visualization of data. The relevant paper is this one [pdf].

Li Wei has generalized the SAX code to handle the N/n not equal an integer case, and to allow alphabet sizes up to 20. Download this zip file for the code and details.

If you want a copy of my SAX time series/Shape tutorial, download this.

Here is a video of Dr. Keogh giving a talk at Google about using SAX for various problems, including shape mining.

NEWS: Much of the utility of SAX has now been subsumed by iSAX , which is a generalization of SAX that allows indexing and mining of massive datasets. Visit the iSAX page.

the performance SAX enables is amazing, and I think a real breakthrough. As an example, we can find similarity searches using edit distance over 10,000 time series in 50 milliseconds. Ray Cromwell, Timepedia.org
SAX represents the state-of-the-art in time series data streams analysis due to its generality Gaber and Gama, Tutorial PKDD07
In order to characterize the expression waveforms we follow the basic SAX formalism for time-series analysis presented by Keogh and Lin... Androulakis et al.
To circumvent the limitations of our previous work, we now rely on a similarity measure that is based on a recent technique called symbolic aggregate approximation (SAX). Almotairi, Saleh et. al 2007.
(SAX based VizTree is).. a way to do such analysis more systematically Edward Tufte.
The method is based on the notion of so called time signature of the clusters, introduced in Lin & Keogh and obtained using a recent time series analysis method called the Symbolic Aggregate approximation (SAX). Pouget, M. Dacier, J. Zimmerman, A. Clark, and G. Mohay. Journal of Information Assurance and Security 1 (2006) 21-32
"Our goal is to identify those transcripts that share significant components of their expression patterns. In order to do so, we explore the SAX idea of Lin and Keogh... Yang et al..
we take SAX Motif developed by Keogh in order to support a medical expert in discovering interesting knowledge. Kitaguchi, S.
In order to symbolize a street data, we utilize the SAX approach. Jalili and Alipour.
...we examine another interesting query, the Time Relaxed Spatiotemporal Trajectory Join (TRSTJ)... we address the TRSTJ problem using SAX... Bakalov, Hadjieleftheriou and Tsotras.
We have decided to use SAX (to detect sophisticated attack tools ).. SAX is a recent and popular method with interesting proven properties. F. Pouget, G. Urvoy-Keller, and M. Dacier
..we are currently using (Lin and Keoghs SAX) approach to creating discrete data from continuous data. Amy McGovern et al.
(to find repeated patterns in protein unfolding data) ...we adopted a two step approach called SAX Ferreira et al.
..we use SAX and Keogh's Tarzan algorithm to do anomaly detection in network traffic. Kyoji Umemura et. al.
SAX has already prove efficient in a large variety of domains Fabian Pouget, Telecom Paris.
SAX representation of abstracted data makes analysis (of anterior-posterior center of pressure) more easy and accurate. Bhatkar et al.
Our Symbolic Transformation (based on SAX method) can be use to discover novel gene relations by mining similar subsequences in time-series microarray data. Vincent Shin-Mu Tseng
..we use SAX bitmap matrices to compute an anomaly score for acoustic signals, enabling the extraction of bird vocalizations and other acoustic events Kasten, McKinley and Gage. 2007
Using the time-series data as an input, it takes too much computation amount to extract motifs from the human motion information. Therefore, we use Symbolic Aggregate approXimation (SAX) .Araki , Arita and Taniguchi 2006
SAX has the advantage of dimensionality and noise reductions. It also allows real valued data to remain the original characteristics with only an infinitesimal time and space overhead...we therefore use it for to determine behavior of system... Lavangnananda and Wongwattanakarn. SMCai07.
SAX demonstrates some promising properties for the field of anomaly detection in a marine engine. Morgan, Liu, Turnbull, and Brown 2007.
..motivated by recent advances in the symbolic representation of streaming data (SAX), effectively reduces the dimensionality of.. Annu. Rev. Biomed. Eng. 2007.
(we use SAX to create a) ..secure multiparty protocol for the privacy preserving pattern discovery problem. Costa da Silva and Klusch 2007.
By using SAX with the sensor network data, we are able to detect such complex patterns with good accuracy .. SAX is a very mature and robust solution for mining time-series data. Zoumboulakis and Roussos 2007
we apply the (SAX based) motif discovery approach the analysis of responses obtained by tactile stimulation of different body areas. Fabri et al. IJCNN07
We extend the SAX approach.. to support Query-by-Singing/Humming. Duda, Nurnberger and Stober (2007).
We use an algorithm based on SAX (Symbolic Aggregate approXimation) to discover human skills.. Makio, Tanaka, and Uehara2007
symbolic aggregate approximation (SAX) outperform other dimensionality reduction techniques like singular value decomposition or discrete fourier transform (SVD, DFT) for time series data.. Assent, Krieger, Afschari and Seidl EDBT 2008
Portions of our work have been inspired by Symbolic Aggregate Approximation (SAX).. Cohen, Bjornsson, Temple, Banker, and Roysam. PAMI 2008
we apply a technique that has demonstrated success with the interpretation of univariate data, named SAX to visualize patterns that may differentiate between medical conditions such as renal and respiratory failure. Ordonez et al. 2008 AMIA
The continuous attributes are transformed into ordered categories using the transformation technique presented in SAX. Ralph Krieger 2008

In [1] we show how to use SAX to find time series discords which are unusual time series. In [2] we consider a special case of SAX, which has an alphabet size of 2, and a word size equal to the raw data, and show that we can use this bit-level representation for a variety of data mining tasks. In [3] we show how to use SAX to create time series bitmaps, which allow visualization of time series data directly within a standard GUI such as MS Windows. In [4] we further show how to use time series bitmaps to do anomaly detection. In [5] we show that SAX can support parameter-lite data mining of time series, including classification and clustering. In [7] we show that SAX can replace standard representations of time series (i.e DWT, DFT) for all classic data mining problems including classification, clustering and indexing. We first used SAX to find time series motifs (exactly, and somewhat fast) in [9], and later showed a blinding fast probabilistic algorithm in [8]. In [10] we tentatively showed how to use SAX to meaningfully cluster time series streams. In [12] we show an application of SAX to a shape mining problem, and in [11] we generalize the time series bitmap concept to more general datasets. In [13] we show how to use SAX to find approximately duplicated shapes (shape motifs) in large databases. Paper [14] is a journal paper reviewing SAX first two years. Paper [15] shows how to find motifs under uniform scaling. Paper [16] introduces iSAX. Paper [17] shows how to do SAX on resource limited sensors.

In [A] the authors "New approaches for representing, analyzing and visualizing complex kinetic mechanisms", they note "The procedure is based on the methodology recently proposed by (Lin and Keogh) for the analysis of multi-dimensional time series". Papers [B.C,D,E] use SAX and random projection (see [8] above) to discover motifs in telemedicine time series. In paper [F] the authors convert plamprint to time series, then to SAX, then they do biometric recognition. Paper [G] says "we take Motif developed by Keogh in order to support a medical expert in discovering interesting knowledge". Paper [H] uses SAX and random projection (see [8] above) to mine motion capture data. Paper [I] uses SAX to find repeated patterns in motion capture data. Paper [J] uses SAX to find rules in time series. Paper [K] uses SAX to find motifs of unspecified length. Paper [L] uses SAX to find repeated patterns in robot sensors. Androulakis et. al. [M] uses SAX for electing Maximally Informative Genes to. Enable Temporal Expression Profiling. In paper [N] the authors us SAX to do Spatiotemporal Trajectory Joins. In [O] the authors use SAX motifs to "analyze respiration wave during cello performance" Paper [P] uses SAX to "detect multi-headed stealthy attack tools". Paper [Q] is using SAX to " Understand the formation of tornadoes"! Paper [R] uses SAX and time series motifs to for the Selection of Informative Genes in Time-Course Gene Expression Data. Paper [S] makes the minor extensions to [8] above, to allow it to handle the multidimensional case. Ph.d Thesis [T] uses SAX for a variety of tasks in network traffic analysis. Paper [U] uses SAX to do Anomaly Detection in Network Traffic. Paper [V] uses SAX to do prediction of severe weather phenomena such as tornados, thunderstorms, hail, and floods. Paper [W] uses a modification of SAX to discover novel gene relations by mining similar subsequences in time-series microarray data. Paper [X] uses SAX for classification of environmental sounds. [Y] uses SAX for financial data mining. Paper [Z] uses SAX for motif discovery. Paper [AA] uses SAX to find motifs in motion capture data. paper [AB] uses SAX based motifs to mine system call sequences. Paper [AB] uses SAX to classify control chart patterns. Papers [AD] and [AE] extend SAX for segmentation of time series into natural episodes. Paper [AF] uses SAX to find anomalies in SAX in a marine engine. Paper [AG] uses SAX for the selection of informative genes. paper [AH] uses SAX to detect complex events in wireless sensor networks. Paper [AI] uses SAX to mine MRIs. Paper [AJ] uses SAX to mine motion capture data. Paper [AK] uses SAX for privacy-preserving discovery of frequent patterns in time series. Paper [AL] uses SAX to find association rules in time series. Paper [AM] uses SAX and Vistree to find patterns in CPU traces. Paper [AN] uses SAX for similarity search. Paper [AO] uses SAX for assessing the wellbeing of unsupervised, vulnerable individuals. Paper [AP] uses SAX for characterizing the mechanism of action of anti-inflammatory drugs. Paper [AQ] uses SAX to visualize patterns that may differentiate between medical conditions such as renal and respiratory failure. Paper [AR] uses SAX to Understand malicious internet traffic by mining honeypot traces. Paper [AS] uses SAX to mine ECG data. Paper [AT] uses SAX to tokenize for gestures.