Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases

The problem of similarity search in large time series databases has attracted much attention recently. It is a non-trivial problem because of the inherent high dimensionality of the data. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a spatial access method. Three major dimensionality reduction techniques have been proposed, Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and more recently the Discrete Wavelets Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call PAA (Piecewise Aggregate Approximation). We theoretically and empirically compare it to the other techniques and demonstrate its superiority. In addition to being competitive with or faster than the other methods our approach has numerous advantages. It is simple to understand and implement, allows more flexible distance measures including weighted Euclidean queries and the index can be built in linear time.