Sang Wook Kim , Dae Hyun Park , Heon Gil Lee

The KIPS Transactions:PartD, Vol. 11, No. 5, pp. 1003-1010, Oct. 2004
10.3745/KIPSTD.2004.11.5.1003,   PDF Download:

Abstract

In this paper, we address efficient processing of subsequence matching in time-series databases. We first point out the performance problems occurring in the index searching of a prior method for subsequence matching. Then, we propose a new method that resolves these problems. Our method starts with viewing the index searching of subsequence matching from a new angle, thereby regarding it as a kind of a spatial-join called a window-join. For speeding up the window-join, our method builds an R*-tree in main memory for a query sequence at starting of subsequence matching. Our method also includes a novel algorithm for joining effectively one R*-tree in disk, which is for data sequences, and another R*-tree in main memory, which is for a query sequence. This algorithm accesses each R*-tree page built on data sequences exactly once without incurring any index-level false alarms. Therefore, in terms of the number of disk accesses, the proposed algorithm proves to be optimal. Also, performance evaluation through extensive experiments shows the superiority of our method quantitatively.

Statistics
Cite this article