We propose an approximation algorithm for efficient correlation search in time series data. In our method, we use Fourier transform and neural network to embed time series into a low-dimensional Euclidean space. The given space is learned such that time series correlation can be effectively approximated from Euclidean distance between corresponding embedded vectors. Therefore, search for correlated time series can be done using an index in the embedding space for efficient nearest neighbor search. Our theoretical analysis illustrates that our method's accuracy can be guaranteed under certain regularity conditions. We further conduct experiments on real-world datasets and the results show that our method indeed outperforms the baseline solution. In particular, for approximation of correlation, our method reduces the approximation loss by a half in most test cases compared to the baseline solution. For top- @math highest correlation search, our method improves the precision from 5 to 20 while the query time is similar to the baseline approach query time.
As far as we know, we are the first to suggest using function approximation, rather than algorithms for feature extraction, for dimension reduction in time series indexing and correlation searching problems. The application of dimension reduction techniques to improve time series correlation search efficiency is first introduced by Agrawal @cite_29 . DFT and discrete wavelet transform (DWT) are the two most commonly used methods. The usage of DFT was introduced by Agrawal @cite_29 , who also constructed @math -tree for indexing on the transformed Fourier coefficients. Chan and Fu @cite_33 , on the other hand, were the first to use wavelet analysis for time series embedding. Regardless of the significant difference between DFT and DWT approaches, it is shown that they have similar performance on query precision in a later paper by Wu @cite_18 . Therefore, in this paper we only consider DFT as our baseline method.
@cite_29 @cite_18 @cite_33
2042591571 2066796814 2163336863 1987262412
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. 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 first performing dimensionality reduction on the data, and 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 Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Piecewise Aggregate Approximation (PAA). 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 other advantages. It is simple to understand and to implement, it allows more flexible distance measures, including weighted Euclidean queries, and the index can be built in linear time. Similarity search in large time series databases has attracted much research interest recently. It is a difficult problem because of the typically high dimensionality of the data.. The most promising solutions involve performing dimensionality reduction on the data, then indexing the reduced data with a multidimensional index structure. Many dimensionality reduction techniques have been proposed, including Singular Value Decomposition (SVD), the Discrete Fourier transform (DFT), and the Discrete Wavelet Transform (DWT). In this work we introduce a new dimensionality reduction technique which we call Adaptive Piecewise Constant Approximation (APCA). While previous techniques (e.g., SVD, DFT and DWT) choose a common representation for all the items in the database that minimizes the global reconstruction error, APCA approximates each time series by a set of constant value segments of varying lengths such that their individual reconstruction errors are minimal. We show how APCA can be indexed using a multidimensional index structure. We propose two distance measures in the indexed space that exploit the high fidelity of APCA for fast searching: a lower bounding Euclidean distance approximation, and a non-lower bounding, but very tight Euclidean distance approximation and show how they can support fast exact searching, and even faster approximate searching on the same index structure. We theoretically and empirically compare APCA to all the other techniques and demonstrate its superiority. Motion estimation and compensation in wavelet domain have received much attention recently. To overcome the inefficiency of motion estimation in critically sampled wavelet domain, the low-band-shift (LBS) method and the complete-to-overcomplete discrete wavelet transform (CODWT) method are proposed for motion estimation in shift-invariant wavelet domain. However, a major disadvantage of these methods is the computational complexity. Although the CODWT method has reduced the computational complexity by skipping the inverse wavelet transform and making the direct link between the critically sampled subbands and the shift-invariant subbands, the full search algorithm (FSA) increases it. In this paper, we proposed two fast multiresolution motion estimation algorithms in shift-invariant wavelet domain: one is the wavelet matching error characteristic based partial distortion search (WMEC-PDS) algorithm, which improves computational efficiency of conventional partial distortion search algorithms while keeping the same estimate accuracy as the FSA; another is the anisotropic double cross search (ADCS) algorithm using multiresolution-spatio-temporal context, which provides a significantly computational load reduction while only introducing negligible distortion compared with the FSA. Due to the multiresolution nature, both the proposed approaches can be applied to wavelet-based scalable video coding. Experimental results show the superiority of the proposed fast motion estimation algorithms against other fast algorithms in terms of speed-up and quality.