Kwang Taek Song, Jae Woo Chang

The KIPS Transactions:PartD, Vol. 8, No. 4, pp. 305-312, Aug. 2001
10.3745/KIPSTD.2001.8.4.305,   PDF Download:

Abstract

Recently, high-dimensional index structures have been required for similarity search in such database applications as multimedia database and data warehousing. In this paper, we propose a new cell-based signature tree, called CS-tree, which supports efficient storage and retrieval on high-dimensional feature vectors. The proposed CS-tree partitions a high-dimensional feature space into a group of cells and represents a feature vector as its corresponding cell signature. By using cell signatures rather than real feature vectors, it is possible to reduce the height of our CS-tree, leading to efficient retrieval performance. In addition, we present a similarity search algorithm for efficiently pruning the search space based on cells. Finally, we compare the performance of our CS-tree with that of the X-tree being considered as an efficient high-dimensional index structure, in terms of insertion time, retrieval time for a k-nearest neighbor query, and storage overhead. It is shown from experimental results that our CS-tree is better on retrieval performance than the X-tree.

Statistics
Cite this article