Woong Kee Loh , Sang Wook Kim

The KIPS Transactions:PartD, Vol. 12, No. 3, pp. 345-354, Jun. 2005
10.3745/KIPSTD.2005.12.3.345,   PDF Download:

Abstract

Subsequence matching is one of the most important operations in the field of data mining. The existing subsequence matching algorithms use only one index, and their performance gets worse as the difference between the length of a query sequence and the size of windows, which are subsequences of a same length extracted from data sequences to construct the index, increases. In this paper, we propose a new subsequence matching method based on index interpolation to overcome such a problem. An index interpolation method constructs two or more indexes, and performs search ing by selecting the most appropriate index among them according to the given query sequence length. In this paper, we first examine the performance trend with the difference between the query sequence length and the window size through preliminary experiments, and formulate a search cost model that reflects the distribution of query sequence lengths in the view point of the physical database design. Next, we propose a new subsequence matching method based on the index interpolation to improve search performance. We also present an algorithm based on the search cost formula mentioned above to construct optimal indexes to get better search performace. Finally, we verify the superiority of the proposed method through a series of experiments using real and synthesized data sets.

Statistics
Cite this article