Cell - based Signature Index Strucutre for Similarity Search in High - Dimensional Data


KIPS Transactions on Computer and Communication Systems, 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
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
K. T. Song and J. W. Chang, "Cell - based Signature Index Strucutre for Similarity Search in High - Dimensional Data," KIPS Journal D (2001 ~ 2012) , vol. 8, no. 4, pp. 305-312, 2001. DOI: 10.3745/KIPSTD.2001.8.4.305.

[ACM Style]
Kwang Taek Song and Jae Woo Chang. 2001. Cell - based Signature Index Strucutre for Similarity Search in High - Dimensional Data. KIPS Journal D (2001 ~ 2012) , 8, 4, (2001), 305-312. DOI: 10.3745/KIPSTD.2001.8.4.305.