Title :
A subsequence matching algorithm supporting moving average transform of arbitrary order in time-series databases using index interpolation
Author :
Loh, Woong-Kee ; Kim, Sang-Wook
Author_Institution :
Dept. of Comput. Sci., Korea Adv. Inst. of Sci. & Technol., Seoul, South Korea
Abstract :
Proposes a subsequence matching algorithm that supports a moving-average transform of arbitrary order in time-series databases. The existing subsequence matching algorithm of C. Faloutsos et al. (1994) requires an index for each moving-average order, which causes serious storage and CPU time overheads. In this paper, we solve the problem using index interpolation. The proposed algorithm can use only a few indexes for pre-selected moving-average orders k, and it performs subsequence matching for an arbitrary order m (⩽k). We prove that the proposed algorithm causes no false dismissal. For selectivities less than 10-2, the degradation of the search performance compared with the fully-indexed case is no more than 17.2% when two out of 128 indexes are used. The algorithm works better with smaller selectivities
Keywords :
database indexing; database theory; interpolation; moving average processes; sequences; statistical databases; string matching; temporal databases; time series; transforms; CPU time overhead; dismissal; index interpolation; moving-average orders; moving-average transform; search performance degradation; selectivity; storage overhead; subsequence matching algorithm; time-series databases; Computer science; Databases; Degradation; Discrete Fourier transforms; Discrete wavelet transforms; Fourier transforms; Indexes; Information technology; Interpolation; Noise reduction;
Conference_Titel :
Database Conference, 2001. ADC 2001. Proceedings. 12th Australasian
Conference_Location :
Gold Coast, Qld.
Print_ISBN :
0-7695-0966-5
DOI :
10.1109/ADC.2001.904462