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. For 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, using funding from NSF Career Award 0237918.

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.

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.

Try this Matlab code snippet:
 startRange = 2;
 stdc= 1;
 endRange = 512;

 table = cell(endRange-startRange,1);
  for r=startRange:endRange
    table{r-startRange+1} = norminv((1:r-1)/r,0,stdc);
  end
This will generate a table of breakpoints from 2 to 512, using std 1.

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
I am a researcher at AT&T, and I have recently been working on a time-series anomaly detection problem involving a very large dataset (hundreds of GB) with about 1500 variables. I have had tried several different approaches, but so far Ive had the most success applying the SAX-bitmap-based approach.. James R. Riehl 2010.
SAX represents the state-of-the-art in time series data streams analysis due to its generality Gaber and Gama, Tutorial PKDD07
In our current research the (SAX) symbolic representation of Lin and Keogh wins out even over well-known approximations... Data Mining Applications in the Automotive Industry. 2010 Kruse, Steinbrecher and Moewes
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.
(for) predictive morphology variations detection in Electrocardiogram Signals The morphology time-series was then converted into a sequence using symbolic aggregate approximation (SAX).. Syed, Indyk and Guttag JLMR 2009
we explicitly focus on the SAX representation, which also provides some significant advantages for mining motifs. Patnaiky, Marwah, Sharma, and Ramakrishnan SIGKDD 2009
We compare wafer patterns using distance measures in SAX and provide severity ranking report to assist engineers in trouble-shooting daily jobs. Lin and Lin 2009
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.
SAX, and more recently iSAX ,has gained traction as the de facto representation for time series in the largespace of representation choice. Armstrong and Drewniak MLDM 2011.
(our work on shape mining is) relying on a general-purpose symbolic representation such as SAX.. Wang and Candan. CIVR 10.
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. (2006)
"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
It's easier to analyze TS in this (SAX) form! Silvia Miksch
..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
We argue that symbolic representations (in particular SAX) are comparatively superior in the data analysis of time series. Moewes & Kruse WCI 2008
With a (SAX) string of symbols describing the trend, analysis is greatly simplified. Field, Stirling , Naghdy and Pan. ACRA 2008
We will often apply this symbolization approach, using the methodology of SAX, with a primary goal of reducing the number of tunable parameters to increase the robustness of the approach Bollt and Skufca 2009
We have shown that a SAX method is particularly useful.. McGregor et al. 2009
In current research the (SAX) symbolic representation of Lin and Keogh wins out even over well-known approximations. Moewes and Kruse 2008
The SAX representation of images renders itself as a better alternativeto the common histogram representation specially for image mining tasks. Al Aghbari.2007
(For the problem of) identification of Global Transcriptional Dynamics we have elected to explore the basic principles of the SAX representation. Yang et al 2009.
We have developed TinySAX - an efficient implementation of SAX using integer arithmetic that makes the application of the technique feasible in tiny devices. Zoumboulakis and George Roussos 2009
SAX is a clever way to discretize signals.. Castro and Ferreira 2007.
A method of prediction .. on SAX utilising an alternative modelling approach known as Markov chaining. Morgan and Liu 2009.
We validated the SAX technique using reflectance indices coming from the band 3 (near infrared) imaging AVHRR-NOOA. The results identified similar periods of flood and drought.. Laurimar Goncalves Vendrusculo 2009
The Symbolic Aggregate approximation (SAX) technique, enables the use of existing text-retrieval techniques and algorithms developed for this context.. Barbosa and Rodrigues 2009
We treat SAX as a black box to which we pass a numeric sensor sequence and it returns a reduced string representation. We then employ the SAX string distance metric .. Zoumboulakis and Roussos 2001
SAX is a time series representation that has proved to be the state-of-the-art technique in time series representation and has been successfully applied in a number of applications.. Sinha, et al 2011
We applied the SAX representation using string lengths of 32.. (for Collaborative Context Prediction) Voigtmann et al. 2011
Specifically, our approach uses aperiodicity information to identify articulations, histograms to compute the density of the peak locations, and a SAX representation to characterize the articulation models Ozaslan and Arcos 2010.
We use five different data sets and classifiers to show that a combination of SAX similarity features and basic features improves the classification accuracy. Siirtola et al. 2011 Patten Recognition Letters.
We use iSAX (indexable Symbolic Aggregate approXimation) to enable interactive searching (<2 sec/example) of a large database (>1,500,000 sec) of everyday user movements on a standard workstation. Kohlsdorf et al 2011
We converted the data into propositional time series by applying the SAX algorithm... Kerr et al. IJCAI11
It should be noted that even the classification results of the SAX feature set outperform the basic feature results by several percentage units. Siirtola et al Pattern Recognition Letters 2011.
We shall use the SAX symbolization in computing (gait).. Parshad et al 2011
We use SAX to measure movement asymmetry symptoms associated with Parkinson’s disease. Sant' Anna. 2011 IEEE Trans Bio Eng
This approach,called SAX, has also been shown to improve clustering due to the smoothing effect of dimensionality reduction. Lee BMC Genomics
each morphological proﬁle is then normalized and discretized. For this purpose, the Symbolic Aggregate approXimation (SAX) is used.. Ciompi et al MICCAI 2011

One way to see the impact of SAX is to consider the number of variants and extensions that have been proposed by others, including ABP-SAX, SAXBop, WeibullSAX, SAXCP, SAX-EFG, SAXO, 1dSAX, aSAX, SAX-GA, SAX-VSM, RASAX, SAX-TD, SFA, ESAX, iSAX, 2DSAX, PSAX, QSAX, SAX2FACE, DPiSAX, , FP_SAX, TFSAX_wPST, CSAX, SAX_SD, SAX-ARM, mtSAX-SEQL, SFA, ESAX, iSAX, geo-iSAX, 2DSAX, PSAX, QSAX, SPTA, rSAX, RSAX, VWSAX, ENSAX, HSAX, TFSAX_wPST, CSAX, SAX_TD, SAX2SEX, SAX++, SAXS and TSAX.

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 a SAX-like (but not SAX) approach 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. Paper [AU] uses SAX for palm print biometrics. Paper [AV] uses SAX for ECG pattern recognition on mobile devices.Paper [AW] uses SAX for large-scale network traffic analysis. Paper [AX] uses SAX for robotic motion segmentaion. Paper [AY] uses SAX for as part of a complexity measure for nonstationary signals. Paper [AZ] uses SAX for mining color distributions in images. Paper [BA] uses SAX for measuring brain states. Paper [BB] uses SAX for mining hurricane data. Paper [BC] uses SAX for quality control in semiconductor manufacturing. Paper [BD] uses SAX as an input to a Markov prediction system. Paper [BE] uses SAX for panic disorder treatment. Paper [BF] uses SAX for analog-circuit fault diagnosis using three-stage preprocessing and time series data. Paper [BG] uses SAX for Mining closed flexible patterns in time-series databases. Paper [BH] uses SAX for clustering industrial heating telemetry. Paper [BI] uses SAX for a computational resource advisory system. Paper [BJ] uses SAX to mine human gait data. Paper [BK] (in Portuguese) uses SAX to mine river levels. Paper [BL] augments SAX for the identification of informative genes in replicated microarray experiments. Paper [BM] uses SAX (actually iSAX) for mining motifs. Paper [BN] uses SAX for shape mining. ...and so on...