Efficient time series matching by wavelets

TLDR

Time series stored as feature vectors can be indexed by multidimensional index trees like R‑Trees for fast retrieval, but the dimensionality curse motivates transformations such as DFT, DWT, KL, or SVD to reduce dimensionality; while DFT, KL, and SVD have been studied, there is no in‑depth study of DWT. The authors aim to investigate the use of the Haar Wavelet Transform for time series indexing. They employ the Haar Wavelet Transform to index time series, preserving Euclidean distance and enabling efficient retrieval. Experiments show that the Haar transform preserves Euclidean distance without false dismissals, outperforms DFT, introduces a similarity model for vertical shifts, and yields a two‑phase method for efficient n‑nearest neighbor queries.

Abstract

Time series stored as feature vectors can be indexed by multidimensional index trees like R-Trees 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 (KL) transform or Singular Value Decomposition (SVD) can be applied. While the use of DFT and K-L transform or SVD have been studied on 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, (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.