Note that this is a longer version of the paper submitted to ICDM 2005. The extra material consists of additional
experiments, additional important references and more detailed and intuitive explanations of some of the algorithms.

HOT SAX: Finding the Most Unusual Time Series
Subsequence: Algorithms and Applications
Eamonn Keogh

Jessica Lin

Ada FuComputer Science & Engineering Department

Department of Computer Science and Engineering

University of California, Riverside

The Chinese University of Hong Kong

Riverside, CA 92521
adafu@cse.cuhk.edu.hk{eamonn, jessica}@cs.ucr.edu

ABSTRACTIn this work, we introduce the new problem of finding timeseries discords. Time series discords are subsequences of alonger time series that are maximally different to all the rest of
the time series subsequences. They thus capture the sense of themost unusual subsequence within a time series. Time series
discords have many uses for data mining, including improving
the quality of clustering, data cleaning, summarization, andanomaly detection. As we will show, discords are particularly
attractive as anomaly detectors because they only require one
intuitive parameter (the length of the subsequence) unlike mostanomaly detection algorithms that typically require many
parameters. While the brute force algorithm to discover timeseries discords is quadratic in the length of the time series, weshow a simple algorithm that is 3 to 4 orders of magnitude fasterthan brute force, while guaranteed to produce identical results.
We evaluate our work with a comprehensive set of experiments.
In particular, we demonstrate the utility of discords with
objective experiments on domains as diverse as Space Shuttle
telemetry monitoring, medicine, surveillance, and industry, andwe demonstrate the effectiveness of our discord discovery
algorithm with more than one million experiments, on 82
different datasets from diverse domains.

Keywords
Time Series Data Mining, Anomaly Detection, Clustering.

1. INTRODUCTION
The previous decade has seen hundreds of papers on time series
similarity search, which is the task of finding a time series thatis most similar to a particular query sequence [7]. In this work,
we pose the new problem of finding the sequence that is least
similar to all other sequences. We call such sequences timeseries discords. Figure 1 gives a visual intuition of a time series
discord found in a human electrocardiogram.
The fact that the discord in Figure 1 coincides with the location
annotated by a cardiologist as containing an anomalous
heartbeat hints at one possible use of discords.

ECG qtdb/sel102 (excerpt)
0

200

400

600

800

1000

1200

1400

Figure 1: The time series discord found in an excerpt ofelectrocardiogram qtdb/sel102 (marked in bold line).
The location of the discord exactly coincides with apremature ventricular contraction
As we shall show, time series discords are superlative anomaly
detectors, able to detect anomalies in domains as diverse as
Space Shuttle telemetry, industry, and medicine. One reason
why discords are particularly suited for the increasingly
important problem of anomaly detection is that they only
require a single intuitive parameter, the length of thesubsequences to consider. In contrast, many other anomaly
detection algorithms require 3 to 7 unintuitive parameters [8].
With so many parameters to set, we need access to hugeamounts of training data, even then, avoiding overfitting
remains a challenge.
Time series discords have other uses. Clustering algorithms canoften benefit from removing a handful of tricky cases, which
can be summarized separately [3]. We could attempt to define
these “tricky cases” as ones that do not belong to any cluster;
however, this opens the possibility of a chicken and egg
paradox. This effect has been noted in clustering points in kdimensional space, but it is also true for time series, and theremoval of discords offers a solution.
This paper makes two fundamental contributions in discovering
unusual time series subsequences. First, while the idea of the“most unusual subsequence” is intuitive, great care must be
taken in creating a workable definition, otherwise, we will be
plagued with uninteresting pathological solutions. We introduce
such a definition here and validate it in domains as diverse as
medicine, surveillance, and space telemetry. Second, the bruteforce algorithm to discover the most unusual subsequencerequires a quadratic “all to all” comparison, which is untenable
for large real-world datasets. We introduce a simple algorithm
that can achieve 3 to 4 orders of magnitude speedup on real
problems.
The rest of the paper is organized as follows. In Section 2, we
review related work and discuss some background material
before introducing our formal definition of time series discords.
In Section 3, we consider the brute-force algorithm for finding
discords, and introduce a general framework for speeding up thesearch based on admissible pruning and reordering the order inwhich the search examines the subsequences. Section 4
introduces a particular reordering strategy based on examining asymbolic version of the data. We perform an extensive
empirical evaluation in Section 5 to demonstrate both the utilityof discords and our ability to find them quickly. Finally, Section
6 offers some conclusions and suggestions for future work.

2. RELATED WORK AND BACKGROUND
Our review of related work is exceptionally brief because we areconsidering a new problem. Most real valued time series
problems such as motif discovery [1][4][9], longest common
subsequence matching, sequence averaging, segmentation,indexing [7], etc. have approximate or exact analogues in thediscrete world, and have been addressed by the text processing
or bioinformatics communities. However, time series discords
do not appear to have a discrete version. Note that thesuperficially similar sounding Furthest (Sub)String Problem
requires us to build a string, not to find one in the data [12].

2.1 Notation
For concreteness, we begin with a definition of our data type ofinterest, time series:
Definition 1. Time Series: A time series T = t1,…,tm is anordered set of m real-valued variables.
For data mining purposes, we are typically not interested in anyof the global properties of a time series; rather, we are interested
in local subsections of the time series, which are called
subsequences.
Definition 2. Subsequence: Given a time series T of length
m, a subsequence C of T is a sampling of length n ≤ m ofcontiguous position from T, that is, C = tp,…,tp+n-1 for 1 ≤ p≤ m – n + 1.
Since all subsequences may potentially be discords, anyalgorithm will eventually have to extract all of them; this can beachieved by use of a sliding window.
Definition 3. Sliding Window: Given a time series T oflength m, and a user-defined subsequence length of n, allpossible subsequences can be extracted by sliding a windowof size n across T and considering each subsequence Cp .
Since our task is to find the most distant subsequence undersome distance measure Dist(C,M), we will take the time todefine distance.
Definition 4. Distance: Dist is a function that has C and M
as inputs and returns a nonnegative value R, which is said tobe the distance from M to C. For subsequent definitions towork we require that the function D be symmetric, that is,Dist(C,M) = Dist(M,C).
While the definition of a distance is obvious and intuitive, weneed it to exclude trivial matches. In general, the best matches
to a subsequence (apart from itself) tend to be located one or
two points to the left or the right of the subsequence in question.
Such matches have previously been called trivial matches[1][4][9]. As we shall see, it is critical when finding discords to
exclude trivial matches; otherwise, almost all real datasets havedegenerate and unintuitive solutions. We will therefore take thetime to formally define a non-self match.
Definition 5. Non-Self Match: Given a time series T,
containing a subsequence C of length n beginning at position
p and a matching subsequence M beginning at q, we say that

M is a non-self match to C at distance of Dist(M,C) if | p – q|
≥ n.
We can most easily see the importance of non-self matches forthe problem at hand if we consider the analogy of the problem
in the discrete world. Consider the following string:abcabcabcabcXXXabcabcabacabc
The eye is immediately drawn to the subsequence of “X”, whichsurely forms the discord here. However, if we assume a sliding
window length of 3, and that our distance measure is thehamming distance, then the subsequence that is farthest from its
nearest neighbor subsequence is “bac”. Below, the string isannotated by subscripts that give the distance to the nearest
neighbor for each subsequence of length 3:
a0b0c0a0b0c0a0b0c0a0b1c1X1X1X1a0b0c0a0b0c0a1b2a1c0a b c
This unexpected and unintuitive result is caused by allowing
trivial matches. While the subsequence XXX may appear
unusual, it is only 1 unit distance from the subsequence XXa,
which shares two elements simply shifted by one place. We cansee the difference this makes by annotating the string with thenon-self match distance to its nearest neighbor subsequence.
a0b0c0a0b0c0a0b0c0a0b1c2X3X2X1a0b0c0a0b0c0a1b2a1c0a b c
Here the results are much more intuitive. While it is a simple
and contrived example on discrete data, as we shall see,identical remarks apply to real world, real valued data. Note thatthe idea that one must exclude “partial self” comparisons inorder to create meaningful definitions is well known in thebioinformatics community [19] and increasingly understood in
the time series data mining community [1][4][9][17][18]. We
will therefore use the definition of non-self matches to define
time series discords:
Definition 6. Time Series Discord: Given a time series T, thesubsequence D of length n beginning at position l is said tobe the discord of T if D has the largest distance to its nearest
non-self match. That is, ∀ subsequence C of T, non-selfmatch MD of D, and non-self match MC of C, min(Dist(D,MD)) > min(Dist(C, MC)We will denote the location of the discord as D.l and the
distance to the nearest non-self matching neighbor as D.dist.
The length of the discord we denote as Dn.
We may be interested in examining the top K discords, which
we define as:
Definition 7. Kth Time Series Discord: Given a time series T,
the subsequence D of length n beginning at position p is theKth-discord of T if D has the Kth largest distance to its nearest
non-self match, with no overlapping region to the ith discord
beginning at position pi, for all 1 ≤ i < K. That is, | p – pi | ≥ n.
We have deliberately omitted naming a distance function up to
this point for generality. For concreteness, we will use theubiquitous Euclidean distance measure throughout the rest of
this paper [4][7].
Definition 8. Euclidean Distance: Given two time series Q
and C of length n, the Euclidean distance between them isdefined as:Dist (Q , C ) ≡ ∑ (q i − ci )
n

2

i =1

Each time series subsequence is normalized to have mean zeroand a standard deviation of one before calling the distancefunction, because it is well understood that in virtually allsettings, it is meaningless to compare time series with different
offsets and amplitudes [7].

2.2 Some Properties of Time Series Discords
Here, we discuss some properties of time series discords toenhance the readers’ understanding of them and to discountsome possible research directions for finding algorithms forquickly locating them.

2.2.1 Discords are not necessary found in sparse space
The idea of considering time series subsequences as points inspace has long been exploited by dozens of indexing techniques[7], so one might imagine that such a representation would be
useful for the task at hand. We could simply project our timeseries into n-dimensional space and use existing outlier
detection methods [10][3]. The problem with this idea is theunintuitive fact that discords do not necessarily live in sparseareas of n-dimensional space (Conversely, repeated patterns do
not necessarily live in dense parts of the n-dimensional space[1][4][9]). The full explanation has consequences for otherproblems and is perhaps deserving of a separate paper; however,
here, we content ourselves with a visual example and a brief
explanation. In Figure 2, we consider a simple time seriesconsisting of a slightly noisy sine wave. We introduce an“anomaly” of length 50 by shifting the entire second half of thetime series.

synthetic datan = 50
0

100

200

300

400

500

600

700

800

900

1000

150
100
50

density02

non-self distance
1
0

0

100

200

300

400

500

600

700

800

900

1000

Figure 2: (Top) A synthetic time series with an obvious
anomaly. (Middle) The local density of subsequences oflength 50, measured by calculating the number ofmatching subsequences within a range of 2. (Bottom).
The non-self match to the nearest neighbor for all
subsequences of length 50
We can now extract all subsequences of length 50, project theminto 50-dimensional space and measure the local density aroundeach subsequence. Surprisingly, the anomaly is not in thesparsest (or in any other way remarkable) region of space.
However, note that the definition of non-self match that is at theheart of time series discords clearly identifies the anomalous
region.
The explanation of this unintuitive finding harkens back to theidea of trivial matches. Consider a subsequence C located at tp
that is “simple”, that is to say it has only one or two features
such as peaks or valleys. This simple subsequence is very closein n-dimensional space to the subsequences beginning at tp+1, tp1, tp+2, etc. In contrast, consider a subsequence M located at tq
that is “complex”, that is to say it has many features such as

peaks or valleys. This complex subsequence is relatively far
from subsequences beginning at tq+1, tq-1, tq+2, etc. In otherwords, simple (and smooth) shapes appear to be in denseneighborhoods because we over-count shifted versions of them.
This problem prevents us for using existing density basedalgorithms to find time series discords. Note that even if current
density based algorithms could be adapted to consider non-self
distance, most of them degrade to quadratic time complexity forhigh dimensionality data.

2.2.2 Discords results are non combinable
Several generic paradigms for solving problems rely on theability to decompose a problem into smaller sub-problems,
which can be solved and admissibly recombined. Depending on
the exact definitions, such techniques are variously called
dynamic programming, divide and conquer, bottom-up, etc [5].
Unfortunately, as we show below, such ideas are unlikely tohelp us efficiently find discords.
Imagine that we break a time series T into two sections, A and B,
and that we find the discords for both sections, recording theirlocations as A.l, B.l and values as A.dist and B.dist, respectively.
Furthermore, imagine that we now concatenate A and B toreproduce the original time series T (for simplicity, let us
assume that when the discord for T is discovered, it will not
span the end of A and the beginning of B). What can we now
say about the discord for T? Surprisingly, the answer is very
little. We cannot assume that it will be either in location A.l or
in location |A| + B.l, because both of the two previously
discovered discords may have good matches in the othersection. All we can do is give weak bounds. The value of T.dist
is at most max(A.dist, B.dist). The lower bound of T.dist is atrivial zero (To see this, imagine A = B). As to the location ofT.l, we can say nothing.

If we consider the complementary situation, where we know thediscord information T.l and T.dist for T, and we split into two
new time series A and B, we are similarly frustrated. Assume
that the discord from T happened to fall into A. We can lower
bound A.dist as being greater than or equal to T.dist, but wecannot provide an upper bound. In addition, we can say nothing
about the location of A.l. As for B.dist and B.l, we can say
nothing.
A combination of these two results also frustrates any thought of
exploiting a sliding window algorithm, since ingesting andegressing a single point can change the location and value of the
discords.
The above results suggest that existing algorithms/paradigms areof little utility for finding discords. This motivates theintroduction of an original algorithm in the next section.

3. FINDING TIME SERIES DISCORDS
The brute force algorithm for finding discords is simple andobvious. We simply take each possible subsequence and find the
distance to the nearest non-self match. The subsequence that has
the greatest such value is the discord. This is achieved with
nested loops, where the outer loop considers each possible
candidate subsequence, and the inner loop is a linear scan to
identify the candidate’s nearest non-self match. For clarity, thepseudo code is shown in Table 1.

Table 2: Heuristic Discord Discovery.

Table 1: Brute Force Discord Discovery.
1

Function [dist, loc ]= Brute_Force(T, n)1

Function [dist, loc ]= Heuristic_Search(T, n, Outer, Inner )2

best_so_far_dist = 02

best_so_far_dist = 0

3

best_so_far_loc = NaN

3

best_so_far_loc = NaN

4
5

4
For p = 1 to |T | - n + 1

6nearest_neighbor_dist = infinity

7

For q = 1 to |T | - n + 1

8

IF | p – q | ≥ n

9

12

5

// Begin Outer Loopnearest_neighbor_dist = infinity// Begin Inner Loop

7

For Each q in T ordered by heuristic Inner // Begin Inner Loop// non-self match?

89

nearest_neighbor_dist = Dist (tp,…,tp+n-1, tq,…,tq+n-1)

10

IF | p – q | ≥ n// non-self match?

IF Dist (tp,…,tp+n-1, tq,…,tq+n-1) < best_so_far_dist
Break// Break out of Inner Loop

11

End

// End non-self match test

12

IF Dist (tp,…,tp+n-1, tq,…,tq+n-1) < nearest_neighbor_dist// End Inner Loop

13

End
End

For Each p in T ordered by heuristic Outer

6

IF Dist (tp,…,tp+n-1, tq,…,tq+n-1) < nearest_neighbor_dist

1011// Begin Outer Loop

13

End

14

IF nearest_neighbor_dist > best_so_far_dist

1415

best_so_far_dist = nearest_neighbor_dist

15

16

best_so_far_loc = p

16

End

17

IF nearest_neighbor_dist > best_so_far_dist

17

End

18

End

19

Return[ best_so_far_dist, best_so_far_loc ]// End Outer Loop

Note that the algorithm requires exactly one parameter, thelength of subsequences to consider. The algorithm is easy to
implement and produces exact results. However, it has one fatal
flaw for data mining. It has O(m2) time complexity which issimply untenable for even moderately large datasets.
The following two observations offer hope to improve thealgorithm’s running time.
• Observation 1: In the inner loop, we don’t actually needto find the true nearest neighbor to the current candidate.
As soon as we find any subsequence that is closer to thecurrent candidate than the best_so_far_dist, we can abandon
that instance of the inner loop, safe in the knowledge thatthe current candidate could not be the time series discord.
• Observation 2: The utility of the above optimization
depends on the order which the outer loop considers thecandidates for the discord, and the order which the inner
loop visits the other subsequences in its attempt to find asequence that will allow an early abandon of the inner loop.
While these are simple ideas and only minor modifications of
the original algorithm, for concreteness, we will make themclear. The pseudo code is shown in Table 2.
Note that the input has been augmented by two heuristics, one todetermine the order in which the outer loop visits thesubsequences, and one to determine the order in which the inner
loop visits the subsequences. Note that the heuristic for the outer
loop is used once, but the heuristic for the inner loop takes thecurrent candidate into account, and is thus invoked to produce a
new ordering for every iteration of the outer loop.
We have now reduced the discord discovery problem into a
generic framework where all one needs to do is to specify theheuristics. Note that we should not attempt to “cheat” thealgorithm. We could provide very good heuristic orderings if weare allowed to completely solve the brute force problem eachtime the heuristic functions are invoked! However this is simply
hiding the time complexly in a different part of theimplementation. We must therefore insist that the Outerheuristic (invoked only once) takes at most O(m) to calculate
and the Inner heuristic (invoked m-n times) takes O(1). Notethat this requirement precludes the possibility of using R-trees,
K-d trees or other classic indexing algorithms [7][15].

nearest_neighbor_dist = Dist (tp,…,tp+n-1, tq,…,tq+n-1)
EndEnd// End non-self match test// End Inner Loop18

best_so_far_dist = nearest_neighbor_dist19

best_so_far_loc = p

20

End

21

End

22

Return[ best_so_far_dist, best_so_far_loc ]// End Outer Loop

To gain some intuition into our new algorithm, and to hint at our
eventual solution to this problem, let us consider 3 possible
heuristic strategies:• Random: We could simply have both the Outer and Inner
heuristics randomly order the subsequences to consider. It
is difficult to analyze this strategy since its performance isbounded from below by O(m) and from above by O(m2)(see below for explanation) and depends on the data.
However, empirically it works reasonably well. The
conditional test on line 9 of Table 2 is often true and theinner loop can be abandoned early, considerably speedingup the algorithm.
• Magic: In this hypothetical situation, we imagine that afriendly oracle gives us the best possible orderings. These
are as follows: For Outer, the subsequences are sorted bydescending order of the non-self distance to their nearest
neighbor, so that the true discord is the first object
examined. For Inner, the subsequences are sorted inascending order of distance to the current candidate. For
the Magic heuristics, the first invocation of the inner loop
will run to completion. Thereafter, all subsequent
invocations of the inner loop will be abandoned during thevery first iteration. The time complexity is thus one
occurrence of m-n+1 steps for the first inner loop, and m-n
occurrences of the O(1) step of each subsequent invocationof the inner loop, giving a total time complexity of O(m) +O(m) or just O(m). Note that we have m ≫n.
• Perverse: In this hypothetical situation, we imagine that aless than friendly oracle gives us the worst possibleorderings. These are identical to the Magic orderings withascending/descending orderings reversed. In this case, weare back to the original O(m2) time complexity, and wewaste some time in the conditional tests on line 9 of Table 2.
These results are something of a mixed bag for us. They suggestthat a linear time algorithm is possible, but only with the aid ofsome very wishful thinking. The Magic heuristic requires aperfect ordering of subsequences in the inner loop, and any
perfect ordering (i.e., sorting) requires at least O(mlogm).
Furthermore, the only known way to produce the perfectordering of subsequences in the outer loop requires O(m2) work,but we are only allowed O(m) time. The following two
observations, however, offer us some hope for a fast algorithm:• Observation 3: In the outer loop, we do not actually need toachieve a perfect ordering to achieve dramatic speedup. All
we really require is that among the first few subsequences
being examined, we have at least one that has a large distanceto its nearest neighbor. This will give the best_so_far_dist
variable a large value early on, which will make theconditional test on line 9 of Table 2 be true more often, thus
allowing more early terminations of the inner loop.
• Observation 4: In the inner loop, we also do not actually needto achieve a perfect ordering to achieve dramatic speedup. All
we really require is that among the first few subsequences
being examined we have at least one that has a distance to thecandidate sequence being considered that is less than thecurrent value of the best_so_far_dist variable. This is asufficient condition to allow early termination of the inner loop.
We can imagine a full spectrum of algorithms, which only differ
by how well they order subsequences relative to the Magicordering. This spectrum spans {Perverse…Random…Magic}.
Our goal then is to find the best possible approximation to the
Magic ordering, which is the topic of the next section.
At the risk of redundancy, we again emphasize that this search
problem requires a specialized solution, and we cannot leverage
off the huge literature on time series similarity search [7]. KdTrees, R-trees and their many variants require O(log(m)) time
per lookup, but we can spare only O(1) time. In any case, thesesearch algorithms support nearest neighbor search, whereas all
we require here is “near-enough” neighbor search, as noted inobservation 4.

4. APPROXIMATIONS TO MAGIC
Before we introduce our techniques for approximating theperfect ordering returned by the hypothetical Magic hueristics,
we must briefly review the Symbolic Aggregate ApproXimation(SAX) representation of time series introduced in [13]. While
there are at least 200 different symbolic approximation of timeseries in the literature, SAX is unique in that it is the only one
that allows both dimensionality reduction and lower boundingof Lp norms. Since its relatively recent introduction, SAX has
become an important tool in the time series data mining toolbox.
It has been used to find time series motifs [4][18], to mine rules
in health data [1], for anomaly detection [8], to extract featuresfrom a hepatitis database [9], for visualization [11][14], and ahost of other data mining tasks.

4.1 A Brief Review of SAX
A time series C of length n can be represented in a wdimensional space by a vector C = c1 ,K, cw . The ith element of
C is calculated by the following equation:ci = wn

ni
w

∑c

j

j = wn ( i −1) +1

In other words, to transform the time series from n dimensions
to w dimensions, the data is divided into w equal sized “frames.”
The mean value of the data falling within a frame is calculated
and a vector of these values becomes the dimensionalityreduced representation. This simple representation is known as
Piecewise Aggregate Approximation (PAA).

Having transformed a time series into the PAA representation,
we can apply a further transformation to obtain a discrete
representation. It is desirable to have a discretization techniquethat will produce symbols with equiprobability [4][8]. In
empirical tests on more than 50 datasets, we noted that
normalized subsequences have highly Gaussian distribution[13], so we can simply determine the “breakpoints” that willproduce equal-sized areas under Gaussian curve.
Definition 9. Breakpoints: Breakpoints are a sorted list of
numbers Β = β1,…,βa-1 such that the area under a N(0,1)
Gaussian curve from βi to βi+1 = 1/a (β0 and βa are definedas -∞ and ∞, respectively).
These breakpoints may be determined by looking them up in astatistical table. For example, Table 3 gives the breakpoints forvalues of a from 3 to 5.
Table 3: A lookup table that contains the breakpoints
that divides a Gaussian distribution in an arbitrary
number (from 3 to 5) of equiprobable regions
βi

a

3

4

5

β1

-0.43

-0.67

-0.84

β2

0.43

0

-0.25

0.67

0.25

β3
β4

0.84

Once the breakpoints have been obtained we can discretize atime series in the following manner. We first obtain a PAA of
the time series. All PAA coefficients that are below the smallest
breakpoint are mapped to the symbol “a”, all coefficients
greater than or equal to the smallest breakpoint and less than thesecond smallest breakpoint are mapped to the symbol “b”, etc.
Figure 3 illustrates the idea.
1.5

c

1

c

c

0.5

b

b

0

b

-0.5

a

-1

a

-1.5
0

20

40

60

80

100

120

Figure 3: A time series (thin black line) is discretized byfirst obtaining a PAA approximation (heavy gray line)
and then using predetermined breakpoints to map the
PAA coefficients into symbols (bold letters). In theexample above, with n = 128, w = 8 and a = 3, the timeseries is mapped to the word cbccbaab
Note that in this example, the 3 symbols, “a”, “b” and “c” areapproximately equiprobable as we desired. We call theconcatenation of symbols that represent a subsequence a word.
Definition 10. Word: A subsequence C of length n can be
represented as a word Cˆ = cˆ1 ,K, cˆw as follows. Let αi denotethe ith element of the alphabet, i.e., α1 = a and α2 = b. Thenthe mapping from a PAA approximation C to a word Cˆ isobtained as follows:cˆi = αiiff

β j −1 ≤ ci < β jWe have now completely defined SAX representation. Note that
our observation that normalized subsequences have highly
Gaussian distribution [13], is not critical to correctness of any of
the algorithms that use SAX, including the ones in this work. A
pathological dataset that violates this assumption will only
affect the efficiency of the algorithms.

4.2 Approximating the Magic Outer Loop
We begin by creating two data structures to support ourheuristics. We are given n, the length of the discords in advance,
and we must choose two parameters, the cardinality of the SAX
alphabet size a, and the SAX word size w. We defer a
discussion of how to set these parameters until later in thissection, but note that the values of α and w only affect theefficiency of our algorithm, not the final result, which depends
only on the user supplied length of the discord.
We begin by creating a SAX representation of the entire timeseries, by sliding a window of length n across time series T,
extracting subsequences, converting them to SAX words, andplacing them in an array where the index refers back to theoriginal sequence. Figure 4 gives a visual intuition of this,where both a and w are set to 3.
Raw time series

0

500

1000

1500

2000

4.3 Approximating the Magic Inner Loop

2500

Subsequence extracted
C1
Converted to SAX

^ caa
C1

Inserted into array

1

c

a

a

3

2

c

a

b

1

3

c

a

a

3

::

::

::

::

::

Augmented Trie
c
c

a
::

::

::

::

((m – n)) -1

c

b

b

a

c

b

1

((m – n)) +1

b

c

a

2

b

9 (m – n) -1

b

2

a

2

((m – n)

77

a
c

::
c

b
a
c

b

1 3

731

c
b
c

a

SAX symbol, then both data structures are significantly smaller
than the raw time series data they were derived from.
We can now state our Outer heuristic; we scan the rightmost
column of the array to find the smallest count mincount (itsvalue is virtually always 1). The indices of all SAX words that
occur mincount times are recorded, and are given to the outer
loop to search over first. After the outer loop has exhausted thisset of candidates, the rest of the candidates are visited in random
order.
The intuition behind our Outer heuristic is simple. Unusualsubsequences are very likely to map to unique or rare SAX
words. By considering the candidate sequences that map tounique or rare SAX words early in the outer loop, we have an
excellent chance of giving a large value to the best_so_far_dist
variable early on, which (as noted in observation 3) will makethe conditional test on line 9 of Table 2 be true more often, thus
allowing more early terminations of the inner loop.

23 (m – n)+1cFigure 4: The two data structures used to support theInner and Outer heuristics. (left) An array of SAX
words, where the last column contains a count of how
often each word occurs in the array. (right) An excerptof an trie with leaves that contain a list of all arrayindices that map to that terminal node
Note that the index goes from 1 to (m – n) + 1, because the rightedge of n-length sliding window “bumps” against end of the mlength time series.
Once we have this ordered list of SAX words, we can imbed
them into an augmented trie where the leaf nodes contain alinked list index of all word occurrences that map there. The
count of the number of occurrences of each word can be mappedback to the rightmost column of the array. For example, in
Figure 4, if we are interested in the word caa, we visit the trie todiscover that it occurs in locations 1, 3, and 731. If we areinterested in the word that occurs at a particular location, let’ssay (m – n) - 1, we can visit that index in the array and discoverthat the word cbb is mapped there. Furthermore, we can see by
examining the rightmost column that there are a total of 2
occurrences of that particular word (including the one we are
currently visiting). However, if we want to know the location of
the other occurrence, we must visit the trie.
Surprisingly, both data structures can be created in time andspace linear in the length of T [1][16]. In fact, if we takeadvantage of the fact that we only need ⎡log2(a)⎤ bits for each

Our Inner heuristic also leverages off the two data structures
shown in Figure 4. When candidate i is first considered in theouter loop, we look up the SAX word that it maps to, by
examining the ith word in the array. We then visit the trie andorder the first items in the inner loop in the order of the elementsin the linked list index found at the terminal nodes. For example,
imagine we are working on the problem shown in Figure 4. If
we were examining the candidate C731 in the outer loop, we
would visit the array at location 731. Here we would find the
SAX word caa. We could use the SAX values to traverse thetrie to discover that subsequences 1, 3, 731 map here. These 3
subsequences are visited first in the inner loop (note that line 8of Table 1 prevents 731 from being compared to itself). After
this step, the rest of the subsequences are visited in random
order.
The intuition behind our Inner heuristic is also simple.
Subsequences that have the same SAX encoding as thecandidate subsequence are very likely to be highly similar (thisfact is at the heart of more than 20 research efforts[1][4][8][9][14][17]). As noted in observation 4, we just need tofind one such subsequence that is similar enough (has a distanceto the candidate than the current value of the best_so_far_dist
variable) in order to terminate the inner loop.

4.4 Minor Optimizations and Parameter Setting
There are several minor optimizations we can apply to theheuristic search algorithm. For example, imagine we areconsidering candidate Ci in the outer loop, and as we traverse
through the inner loop, we find that subsequence Cj is closeenough to it to allow early abandonment. In addition to saving
time with the early termination, we can also delete Cj from thelist of candidates in outer loop (if it has not already been
visited). The key observation is that since we are assuming asymmetric distance measure, if nearness to Cj disqualifies
candidate Ci from being the discord, then the same nearness to
Ci would also disqualify candidate Cj from being the discord.
Empirically, this simple optimization gives a speed-up factor of
approximately 2. In addition, there are several well-known
optimizations to the Euclidean distance that we can use [7].
As noted above, we must choose two parameters, the cardinalityof the SAX alphabet size a, and the SAX word size w. Recall
what it is we want to optimize. We would like the distribution of
the SAX words to be highly skewed, so that the discord will

map to a SAX word that is unique or rare, and all the othersubsequences will map to SAX words that are very frequent.
This is the best situation for both our heuristics. If we choose
very large values of a and/or w, almost all subsequences will
map to unique words; if we choose very small values of a and/or
w, all subsequences will map to just a small handful of words.
Either of these situations is bad for our heuristics.
The good news is that there is little freedom for the a parameter;
extensive experiments carried out by the current authors[4][8][11][13][14] and dozens of other researchers worldwide[1][9][17][18] suggest that a value of either 3 or 4 is best for
virtually any task on any dataset. After empirically confirming
this on the current problem with experiments on more than 50
datasets, we will simply hardcode a = 3 for the rest of this work.
Having fixed a, we performed an exhaustive empiricalexamination of the role of the w parameter. The best value forthis parameter depends on the data. In general, relatively smoothand slowly changing datasets favor a smaller value of w,
whereas more complex time series favor a larger value of w.
The following observations mitigate the problem of parametersetting:• The speedup does not critically depend on w parameter.
After empirically finding the best value on a particular data
we found we could vary the value of w in the range of 60%
to 150% with less than a 12% decrease in speedup.
• Once we learn a good setting on a particular data type, say
ECGs, that setting will also work well on other datasets ofthe same type (assuming the sampling rate is the same).

examining the test dataset.
One could easily imagine
generalizing the discord discovery algorithm to examine only
the test data in the outer loop and only training data in the innerloop. However we wish to concentrate on first proving oursimple intuitive definitions before creating generalizations.

5.1.1 Anomaly Detection in Space Telemetry
We consider the problem of finding anomalies in sensor timeseries. In Figure 5, we see an example of a Space Shuttle
Marotta Valve time series that was annotated as normal by aNASA engineer.
Energizing
Phase

Space Shuttle Marotta
Valve: Normal cycle
De-Energizing Phase

0

100

200

300

400

500

600

700

800

Poppet pulled significantly out of
the solenoid before energizing

Marotta Valve Series I

0

The DeEnergizing
phase isnormal1

We have conducted such experiments and we have made themavailable here [6].

500

1000

1500

2000

2500

3000

3500

4000

4500

5000

Figure 6: An example of an annotated Marotta Valvetime series. The discord discovered (highlighted in bold)exactly corresponds with the expert’s annotation of apremature Poppet withdrawal

5.1 The Utility of Time Series Discords
In this paper, we will only demonstrate the utility of discords asanomaly detectors. We have done extensive successful
experiments in other tasks, such as improving the quality ofclustering and summarization; however, anomaly detection is
unique in that it allows immediate and intuitive visualconfirmation. The additional experiments for other tasks,
together with many extra anomaly detection experiments can befound here [6]. We encourage the interested reader to consult
this site for additional examples and larger and more detailed
figures of the experiments show below.
After much reflection, we have decided not to include
comparisons to other approaches here1. There are two reasonsfor this. Firstly, we simply could not make the other approaches
work well, and we do not wish to seem to be badgering fellow
researchers. To be fair to the other approaches, it is very
difficult to make meaningful comparisons between our method,which requires only one intuitive parameter, and some of therival methods that require 3 to 7 parameters [8], including someparameters for which we may have poor intuition, such as
Embedding dimension, Kernel function, SOM topology or
number of Parzen windows.
The second reason we do not compare to other anomaly
detectors is that most algorithms require a separate training
dataset, whereas our approach finds anomalies while only

1000

The engineer further annotated several other traces of the same
sensor that have several kinds of faults. We first consider aneasy problem; in Figure 6, the expert annotated the last in aseries of 5 energize/deenergize cycles as “Poppet pulled
significantly out of the solenoid before energizing”. The
problem is immediately obvious to even the untrained eye, andthe discord128 completely spans the offending section.

5. EMPIRICAL EVAUALTION
We begin by showing the utility of time series discords for ahost of domains, then go on to show that our algorithm is able tofind discords very efficiently.

900

Figure 5: An example of a Space Shuttle Marotta Valvetime series that was annotated as normal

In Figure 7, we consider a much more subtle problem; once
again we find the discord128, and once again its location exactly
coincides with the expert’s annotation.
M arotta V alve S eries II

500

0

1000

1500

P o p p e t pulle d o ut o f the so le no id b e fo re e ne rg iz ing

2000

3000

2500

3500

4000

4500

5000

Figure 7: Another example of an annotated Marotta
Valve time series.
While the discord discovered(highlighted in bold) exactly corresponds with theexpert’s annotation, it is difficult to see why at this scale
At the scale shown, it is impossible to see what the expert saw
to justify her decision; however, in Figure 8, we can see that thediscord has a “double hump”, whereas the corresponding sectionof the other four cycles have a single hump.
Poppet pulled out of thesolenoid before
energizing

Corresponding
section ofother cycles

Discord

Discord

1500

2000

2500

0

50

100

Figure 8: (Left) A subsection of Figure 7 showing thediscord found. (Right) A Zoom-in of the discord, and thefour corresponding sections form the normal cycles
explains the fault. The engineer noticed the unusual“double hump” which flagged the problem

While we address the efficiency of our algorithm in detail in
Section 5.2, we note in passing that in both cases above, ourapproach was more than 1,600 times faster than brute force
search.

5.1.2 Change Detection in Patient Monitoring
The problem of change detection is fundamentally different
from anomaly detection. In anomaly detection, the task is to find
one or more “different” subsequences that exist in the
background of a normal data. In the problem of change
detection, we assume that the underlying model that produces
the signal changes in some (possibly very subtle) way at various
points. The task is to identify the locations of these change
points.
Time series discords do not appear to be likely candidates forchange detection, since they look at local patterns, whereas mostchange detection algorithms consider global (or at least muchlarger “local”) information. However, we believe that in somesituations, the change in underlying global model may produce
some unusual local shapes because the local pattern must
straddle two different models.
To test this idea, we investigated a time series showing apatient’s respiration (measured by thorax extension), as they
wake up. A medical expert, Dr. J. Rittweger of the Institute forPhysiology, Free University of Berlin, manually segmented thedata. We choose a discord length corresponding to 32 seconds
because we want to span several breaths. In Figure 9, we see theoutcome of the first experiment.
Shallow breaths as waking cycle begins

1st Discord

5.1.3 Anomaly Detection in Electrocardiograms
Electrocardiograms (ECGs) are a time series of the electricalpotential between two points on the surface of the body caused
by a beating heart. They are arguably the important time series,
and as such, there are many annotated test datasets we canconsider. We have already considered the utility of discords in
one ECG in Figure 1. That was a very simple and “clean”
example for clarity; however, it is remarkable how varied andcomplex normal healthy ECGs can be. For example, Figure 11
shows a very complicated signal with remarkable variability
Surprisingly, this ECG contains only one small anomaly, whichis easily discovered by a discord.

BIDMC Congestive Heart Failure Database: Record 15

r
0

5000

1st Discord

3rd Discord

Stage II sleep

15000

In Figure 12, we consider an ECG that has several different
types of anomalies. Here, the first 3 discords exactly line up
with the cardiologist’s annotations. In this figure we could
perhaps spot the anomalies by eye; however, the full time series
is much longer, and impossible to scrutinize without a scrollbar
and much patience.
2nd Discord

2nd Discord

0

10000

Figure 11: An ECG that has been annotated by a
cardiologist (bottom bar) as containing one premature
ventricular contraction. The discord256 (bold line)
exactly coincides with the heart anomaly

Eyes closed, awake/stage I sleep Eyes open, awake

500

1000

1500

2000
MIT-BIH Arrhythmia Database: Record 108

Figure 9: The first 2 discords found in a time series of apatient’s respiration as they wake up. The annotations
show in the boxes at the bottom of the screen areprovided by a medical expert
The 1st discord is a very obvious deep breath taken as the patient
opened their eyes. In contrast, the 2nd discord is much more
subtle and difficult to see at this scale. A zoom-in suggests that
Dr. Rittweger noticed a few shallow breaths that indicated thetransition of sleeping states. In both cases. the discords straddle
the change in sleeping cycle. We tested many such datasets withequally positive results. Figure 10 shows another representative
example.
1st Discord
2nd Discord

Stage II sleep
0

500

1000

1500

Awake Stage I sleep
2000

2500

3000

3500

4000

Figure 10: The first 2 discords found in a time series of apatient’s respiration

r
0

S
5000

10000

r
15000

Figure 12: An excerpt of an ECG that has beenannotated by a cardiologist (bottom bar) as containing 3
various anomalies. The first 3 discord600 (bold lines)
exactly coincides with the anomalies
In the above cases, we simply set the length of the discords to beapproximately one full heartbeat (note that the two datasets havedifferent sampling rates). Although we found that we could
double or half the parameters without affecting the quality of
results, on just a handful of the dozens of ECG datasets we
examined, the discords had a harder time finding the anomalous
heartbeats. We conferred with cardiologist, Dr. Helga Van Herle
M.D., who informed us that heart irregularities can sometimes
manifest themselves at scales significantly shorter than a single
heartbeat. Armed with this knowledge, we searched for discords
at approximately ¼ the length of a single heartbeat. In Figure
13, we show the results of a search with the shorter length
discords.

r

QT Database: Record 0606
0

500

1000

1500

Figure 13: An ECG that has been annotated by a
cardiologist (bottom bar) as containing one premature
ventricular contraction. The discord40 (bold line) exactly
coincides with the heart anomaly
While the result is satisfying in that it immediately locates theanomaly, it is not obvious from the figure that the discord isactually different for the other heartbeats. In Figure 14 (left) we
see a zoom-in of the subsequence surrounding the discord, andwe can see that the discord falls over the ST wave. In Figure 14(right), we manually extracted 4 ST waves from thesubsequence in Figure 13 and clustered them together with thediscord. This makes the source of the anomaly apparent. Notethat in the four normal ST waves, after the brief descending
section, the signal rises monotonically. However, the anomalous
ST wave has an additional local peak caused by a premature
beat, thus justifying the cardiologist’s diagnosis of premature
ventricular contraction.
Rcalled on line 9 in Table 1 and Table 2. A simple analysis of thepseudocode (confirmed with a profiler) tells us that this single
line of code accounts for more than 99% of the running time forboth algorithms. In addition to fairness and reproducibility,
there is another pragmatic reason for this metric. For brute force
search, this number depends only on n and m and can simply be
computed. If we had to actually measure the wall clock time forbrute force search for all the experiments in this work, it would
take several years.
The above metric does not include the time it takes to build thedata structures discussed in Section 4.2; however, we note that
this is a O(m), one time cost. For datasets of a reasonable size(i.e., the datasets shown in Figures 11 or 12), this overhead takes
much less than 0.1% of the total time. Furthermore, as thedatasets get larger, it takes an even smaller percentage of time.
In Figure 16, we compare the brute force algorithm to theheuristic search algorithm in terms of the number of times the
Euclidean distance function on line 9 is called. For the heuristic
search we averaged the results for each setting of dataset/length
over 100 runs on different subsets of the data.

2

1
Q
S

4

r
900

1000

1100

Discord1200

Figure 14: (left) A zoom-in of a section of Figure 13. The
first heartbeat has been annotated with the classic
notation.
(right) Five ST waves from Figure 13(including the discord) hierarchically clusteredlog(number of calls to dist)

3
TP

5.1.4 Power Demand data exploration with discords

Sa
tu
rd
ay
Su
nd
ay

ed
ne
sd
ay
Th
ur
sd
ay
Fr
ida
y

W

M
on
da
y
Tu
es
da
y

The experiments above were performed in domains where
objective answers are readily available. In this section, we
perform an experiment where the only evaluation is theintuitiveness of the discords discovered.
We queried a dataset that measured the power consumption fora Dutch research facility for the entire year of 1997. We wanted
to find the 3 most usual weeks. Note that we did not specify thatweek should begin at certain day or time. We initially guessedthat a length of 750 would cover an entire week; this turns out tobe a little long, but we show this experiment to avoid“polishing” the results. Figure 1 shows the top 3 discords and atypical pattern for reference.
Liberation Day

Ascension Thursday

Dec 25Sunday
0

100

200

300

400

500

600

Typical Week from the Dutch
Power Demand Dataset

700

Good Friday
Easter Sunday

0

100

200

300

400

500

600

700

Figure 15: (left) A typical week from the Dutch power
demand dataset shows the classic 9am to 5pm, Monday
to Friday pattern of power demands. (right) The top 3
discord750 shows unusual weeks in that they all containtwo holidays

5.2 The Utility of Heuristic Ordered Search
It is increasingly recognized that comparing algorithms
performance by examining wall clock or CPU time invites thepossibility of implementation bias [7], which in turn invites thepossibility of irreproducible “improvements.” Instead, we
measure here the number of times that the distance function is

a fa
ctor

10
8

of 2
,902

6
4
2
0

Force
Brute tasets)(all daec gkoski_ walk
om
d
ise
n
a
R
Tickw P_data
ER
el102
qtdbs

1k

2k

4k

le
m, the

8k

ngth

16k

32k

64k

sT
e serieof timFigure 16: The number of calls to the distance function
required by brute force and heuristic search for discord128
over a range of data sizes for 5 representative datasets
Note that as the data sizes increase, the differences get larger.
For a time series of length 64,000, the heuristic algorithm isalmost three thousand times faster than brute force for all
datasets. This experiment is actually pessimistic in that we madesure that the test data did not have any obvious anomalies or
unusual patterns. In general, if there are truly unusual patterns in
the time series, the heuristic algorithm is even faster.
In general, these results strongly suggest that we can reasonably
expect at least 3 orders of magnitude of a speedup for mostproblems. To concretely ground these numbers, consider thefollowing. While our current implementation is in relatively
lethargic Matlab, the experiments shown in Figures 10, 11, and12 take a few seconds using heuristic search, but several hours
using brute force search.
To make sure that the above results were not the result of a
happy coincidence of “easy” datasets and the right setting of thesingle parameter, we repeated the experiment for every dataset
in the UCR Time Series Data Mining Archive over a range ofvalues for n. We tested all datasets that have a length of at least
16,000; there are currently 82 such datasets from a diverse set of
domains. Figure 17 shows the results.

[3] Chen, Z., Fu, A, & Tang J (2004). On Complementarity of700

Cluster and Outlier Detection Schemes. DaWaK: pp 234-243[4] Chiu, B., Keogh, E. & Lonardi, S. (2003). Probabilistic
Speedup over brute force

600
500
400
300
200
100
0
16k

8k

m, thesize of
the

256

4k

database2k

128

lengthiscord
d
e
th
n,
64

Figure 17: The speed obtained over brute force searchfor various discord lengths and database sizes, averaged
over 82 diverse datasets
This experiment produces pessimistic results in that many of thedatasets we averaged over are exceptionally noisy. In addition,
the maximum size of the data (16k) was relatively small toallow us to average over many datasets. Nevertheless the results
support the contention that a minimum speedup of two orders ofmagnitude can be expected for any combination of dataset/n,
and even greater speedup can be expected as the datasets getlarger.

6. CONCLUSIONS AND FUTURE WORKIn this work, we have defined time series discords, a newprimitive for time series data mining. We introduced a novel
algorithm to efficiently find discords and demonstrated theirutility of a host of domains.
Many future directions suggest themselves; most obvious
among them are extensions to multidimensional time series, tostreaming data, and to other distance measures. In addition, fortruly massive datasets, even the large speedups obtained may beinsufficient for real time interaction. We therefore plan toinvestigate an anytime version of our algorithm.

7. ACKNOWLEDGMENTS
We gratefully acknowledge Philip Chan, Matt Mahoney (FIT)
and Bob Ferrell (NASA KSC) for arranging the donation of
Marotta Valve dataset, and all the other donors of datasets. We
also acknowledge assistance from domain experts Dr. Helga
Van Herle and Dr. J. Rittweger, and insightful comments from
Chotirat (Ann) Ratanamahatana.
Reproducible Results Statement: In the interests of competitive
scientific inquiry, all datasets used in this work are available at thefollowing URL [6]. This research was partly funded by the National
Science Foundation under grant IIS-0237918.

8. REFERENCES[1] Bentley. J. L. & Sedgewick. R. (1997). Fast algorithms for
sorting and searching strings. In Proceedings of the 8th Annual
ACM-SIAM Symposium on Discrete Algorithms. pp. 360-369[2] Duchene, F., Garbayl, C. & Rialle. V. (2004). Mining
Heterogeneous Multivariate Time-Series for Learning
Meaningful Patterns: Application to Home Health Telecare.
Laboratory TIMC-IMAG, Facult'e de m'edecine de Grenoble,
France.

Discovery of Time Series Motifs. In the 9th ACM SIGKDDInternational Conference on Knowledge Discovery and Data
Mining. pp 493-498.
[5] Coerman, T. H., Leiserson, C. E. &. Rivest R. L. (1990)
Introduction to Algorithms, McGraw-Hill Company.
[6] Keogh. E. (2005). www.cs.ucr.edu/~eamonn/discords/[7] Keogh, E. & Kasetty, S. (2002). On the need for time series
data mining benchmarks: A survey and empiricaldemonstration. In Proc. of SIGKDD. pp 102-111.
[8] Keogh, E., Lonardi, S. & Ratanamahatana, C. (2004).
Towards Parameter-Free Data Mining. In proceedings of the10th ACM SIGKDD International Conference on Knowledge
Discovery and Data Mining. pp 206-215.
[9] Kitaguchi, S. (2004). Extracting Feature based on Motif from a
Chronic Hepatitis Dataset. In proceedings of the 18th Annual
Conference of the Japanese Society for Artificial Intelligence(JSAI).
[10] Knorr, E., Ng, R. &. Tucakov V. (2000). Distance-Based
Outliers: Algorithms and Applications. VLDB J. 8(3-4): 237253.
[11] Kumar, N., Lolla N., Keogh, E., Lonardi, S., Ratanamahatana,C., & Li, W. (2005). Time-series Bitmaps: A Practical
Visualization Tool for working with Large Time Series
Databases. SIAM Data Mining Conference.
[12] Lanctot, J. K., Li, M., Ma. B., Wang, S., &. Zhang, L (2003).
Distinguishing string selection problems, Information andComputation 185: pp 41–55.
[13] Lin, J., Keogh, E., Lonardi, S., & Chiu, B. (2003). A Symbolic
Representation of Time Series, with Implications for
Streaming Algorithms. In proceedings of the 8th ACM
SIGMOD Workshop on Research Issues in Data Mining andKnowledge Discovery.
[14] Lin, J., Keogh, E., Lonardi, S., Lankford, J. P. & Nystrom, D.
M. (2004). Visually Mining and Monitoring Massive Time
Series. In proceedings of the 10th ACM SIGKDD International
Conference on Knowledge Discovery and Data Mining. pp460-469.
[15] Ratanamahatana, C. & Keogh, E. (2004). Making Time-series
Classification More Accurate Using Learned Constraints. In
proceedings of the 4th SIAM International Conference on Data
Mining.
[16] Sadakane, K., (2000) Compressed text databases with efficientquery algorithms based on the compressed suffix array,
Proceedings of ISAAC’00, LNCS, pp 410–421.
[17] Tanaka, Y. & Uehara, K. (2004). Motif Discovery Algorithm
from Motion Data. In proceedings of the 18th Annual
Conference of the Japanese Society for Artificial Intelligence(JSAI).
[18] Rombo, S. & Terracina, G. (2004). Discovering Representative
Models in Large Time Series Databases. In proceedings of the
6th International Conference On Flexible Query Answering
Systems. pp 84-97[19] Ruzzo W.L, & Tompa M. (1999). A linear time algorithm forfinding all maximal scoring subsequences. In Proc Int ConfIntell Syst Mol Biol.; pp 234-41.