IEEE Transactions on Knowledge and Data Engineering · 2003 · 261 citations · 26 references
ComputingComputer ScienceInformation RetrievalSequence AnalysisTime Series AnalysisComputational Time Series AnalysisSequence Pattern RecognitionSignal ProcessingTime Series ComputationDiscrete Fourier TransformSimilarity SearchTemporal ShiftsTime Series IndexingTime Series Similarity SearchTime WarpingWavelet AnalysisWavelet Transform
We address the handling of time series search based on two important distance definitions: Euclidean distance and time warping distance. The conventional method reduces the dimensionality by means of a discrete Fourier transform. We apply the Haar wavelet transform technique and propose the use of a proper normalization so that the method can guarantee no false dismissal for Euclidean distance. We found that this method has competitive performance from our experiments. Euclidean distance measurement cannot handle the time shifts of patterns. It fails to match the same rise and fall patterns of sequences with different scales. A distance measure that handles this problem is the time warping distance. However, the complexity of computing the time warping distance function is high. Also, as time warping distance is not a metric, most indexing techniques would not guarantee any false dismissal. We propose efficient strategies to mitigate the problems of time warping. We suggest a Haar wavelet-based approximation function for time warping distance, called Low Resolution Time Warping, which results in less computation by trading off a small amount of accuracy. We apply our approximation function to similarity search in time series databases, and show by experiment that it is highly effective in suppressing the number of false alarms in similarity search.
26
R. K. Agrawal, Ramakrishnan Srikant · 2002 · 5.1K citations
The Analysis of Time Series: An Introduction
David A. Dickey, Chris Chatfield · Technometrics · 1991 · 3.6K citations
Computing, Economics, Mathematics +12
Fast subsequence matching in time-series databases
Christos Faloutsos, M. Ranganathan, Yannis Manolopoulos · 1994 · 1.7K citations · Full text