Index interpolation: A subsequence matching algorithm supporting moving average transform of arbitrary order in time-series databases

In this paper we propose a subsequence matching algorithm that supports mov ing average transform of arbitrary order in time-series databases. Moving a verage transform reduces the effect of noise and has been used ill many are as such as econometrics since it is useful in finding the overall trends. T he proposed algorithm extends the existing subsequence matching algorithm p roposed by Faloutsos et al. (SUB94 in short). If we applied the algorithm w ithout any extension, we would have to generate all index for each moving a verage order and would have serious storage arid CPU time overhead. In this paper we tackle the problem using the notion of index interpolation. Index interpolation is defined as a searching method that uses one or more index es generated for a few selected cases and performs searching for all the ca ses satisfying some criteria. The proposed algorithm, which is based on ind ex interpolation, can use only one index for a pre-selected moving average order k and per forms subsequence matching for arbitrary order m (less than or equal to k). prove that the proposed algorithm causes no false dismissa l. The proposed algorithm can also use more than one index to improve searc h performance. The algorithm works better with smaller selectivities. For s electivities less than 10(-2), the degradation of search performance compar ed with the fully-indexed case-which is equivalent to SUB94-is no more than 33.0% when orle index is used, and 17.2% when two indexes are used. Since the queries with smaller selectivities are much more frequent in general da tabase applications. the proposed algorithm is suitable for practical situa tions.