Dimensionality Reduction and Similarity Search in Large Time Series Databases
Li Si Ai · Chinese Journal of Computers · 2005
The problem of similarity search in time series databases has attracted much research interest in the database and data mining communities in the last decade. A systemic method of indexing and similarity searching in time series databases based on Piecewise Polynomial Representation (PPR) is proposed in this paper. The idea is to map each sub-sequence into a small set of multidimensional rectangles in feature space that is spanned by base of linear polynomial. PPR is a linear polynomial representation, and PAA (Piecewise Aggregate Approximation), an well known time series compression technique, is a special case of PPR. PPR is used as an efficient dimensionality reduction technique to permit similarity search over large time series databases without false dismissals. Computational complexity of PPR is O(n). The lower boundaries of search threshold are estimated, and a detailed performance anlysis of proposed method is presented. The experimental results demonstrate that performances of proposed method are superior to that of DFT (Discrete Fourier Transform) and DWT (Discrete Wavelet Transform) based index techniques.