Locating patterns in discrete time series

Kevin B. Pratt

Masters Thesis, Computer Science and Engineering Department, University of South Florida, 2001.


We describe a technique for fast compression of time-series, indexing of the resulting compressed series, and retrieval of series similar to a given pattern. The compression algorithm identifies "important" points of a time-series and discards the other points. It runs in linear time, takes constant memory, and gives good results for a wide variety of time-series. We use the important points not only for compression, but also for indexing a database of time-series, which supports efficient search for patterns and allows the user to control the trade-off between the speed and accuracy of search. The experiments show the effectiveness of the developed technique for identifying patterns in stock prices, meteorological data, and electrocardiograms.