INDEXING OF COMPRESSED TIME SERIES - Data Mining in Time Series Databases - page 43

CHAPTER 3
INDEXING OF COMPRESSED TIME SERIES
Eugene Fink
Computer Science and Engineering, University of South Florida
Tampa, Florida 33620, USA
E-mail: [e-mail]
Kevin B. Pratt
Harris Corporation, 1025 NASA Blvd., W3/9708
Melbourne, Florida 32919, USA
E-mail: [e-mail]
We describe a procedure for identifying major minima and maxima of
a time series, and present two applications of this procedure. The first
application is fast compression of a series, by selecting major extrema
and discarding the other points. The compression algorithm runs in lin-
ear time and takes constant memory. The second application is indexing
of compressed series by their major extrema, and retrieval of series sim-
ilar to a given pattern. The retrieval procedure searches for the series
whose compressed representation is similar to the compressed pattern. It
allows the user to control the trade-off between the speed and accuracy
of retrieval. We show the effectiveness of the compression and retrieval
for stock charts, meteorological data, and electroencephalograms.
Keywords : Time series; compression; fast retrieval; similarity measures.
1. Introduction
We view a time series as a sequence of values measured at equal intervals;
for example, the series in Figure 1 includes the values 20, 22, 25, 22, and
so on. We describe a compression procedure based on extraction of certain
important minima and maxima from a series. For example, we can compress
the series in Figure 1 by extracting the circled minima and maxima, and
discarding the other points. We also propose a measure of similarity between
43