Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases

スポンサーリンク

概要

• 論文の詳細を見る

• In this paper we propose a subsequnce matching algorithm that supports moving average transform of arbitrary order in time-series databases. Moving average tansform reduces the effect of noise and has been used in many areas such as econometrics since it is useful in finding the overall trends. The proposed algorithm extends the exisiting subsequnce matching algorithm proposed by Faloutsos et al. (SUB94 in short). If we applied the algorithm without any extension, we would have to generate an index for each moving average order and would have serious storage and 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 indexes generated for a few selected cases and performs searching for all the cases satisfying some criteria. The proposed algorithm, which is based on index interpolation, can use only one index for a pre-selected moving average order k and performs subseqence matching for arbitrary order m (<__- k). We prove that the proposed algorithm causes no false dismissal. The proposed algorithm can also use more than one index to improve search performance. The algorithm works better with smaller selectivities. For selectivities less than 10^<-2>, the degradation of search performance compared with the fully-indexed case-which is equivalent to SUB94-is no more than 33.0% when one index is used, and 17.2% when two indexes are used. Since the queries with smaller selectivities are much more frequent in general database applications, the proposed algorithm is suitable for practical situations.

• 社団法人電子情報通信学会の論文
• 2001-01-01

著者

• Whang Kyu-young

  The Authors Are With The Electronic Engineering And Computer Science Department Division Of Computer

• Whang Kyu-young

  The Author Is With The Department Of Computer Science Korea Advanced Institute Of Science And Techno

• Kim Sang-wook

  The Author Is With The Division Of Computer Information And Communications Kangwon National Universi

• LOH Woong-Kee

  The authors are with the Electronic Engineering and Computer Science Department, Division of Compute

• Loh Woong-kee

  The Authors Are With The Electronic Engineering And Computer Science Department Division Of Computer

関連論文

• Linearizing Datalog Programs with Multiple Bilinear Rules
• Index Interpolation: A Subsequence Matching Algorithm Supporting Moving Average Transform of Arbitrary Order in Time-Series Databases

スポンサーリンク