|
|
|
 |
|
 |
|
Efficient Time Series Matching by Wavelets
|
K.-P. Chan and
A.W.-C. Fu
View Paper (PDF)
Return to Session 4: Data Mining I
Time series stored as feature vectors can be indexed by
multi-dimensional index trees like R-Tree for fast retrieval. Due to the
dimensionality curse problem, transformations are applied to time series to
reduce the number of dimensions of the feature vectors. Different
transformations like Discrete Fourier Transform (DFT), Discrete Wavelet
Transform (DWT), Karhunen-Loeve (K-L) transform or Singular Value Decomposition
(SVD) can be applied. While the use of DFT and K-L transform or SVD have been
studied in the literature, to our knowledge, there is no in-depth study on the
application of DWT. In this paper, we propose to use Haar Wavelet Transform for
time series indexing. The major contributions are: (1) we show that Euclidean
distance is preserved in the Haar transformed domain and no false dismissal
will occur in range query, (2) we show that Haar transform can outperform DFT
through experiments, (3) a new similarity model is suggested to accommodate
vertical shift of time series, and (4) a two-phase method is proposed for
efficient n-nearest neighbor query in time series databases.
Copyright(C) 2000 ACM
|
|
|
|
|
|
|
