A cell-based index structure for similarity search in high-dimensional feature spaces

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