Y. Feng and A. Makinouchi (Japan)
Multidimensional index, NN search, Clustering
R-tree family is widely used in multimedia databases and spatial databases, in which NN (Nearest Neighbor) search is very popular. This paper proposes an approach to improve R-trees for nearest neighbor search by intro ducing clustering technology. Our study is based on the following observations: (1) the degree of the objects be ing clustered in the leaf nodes is a very important factor on NN search performance; (2) Normally, in R-trees, the objects are not well-clustered in the leaf nodes. Although some packing algorithms for R-trees have been proposed, all of them try to pack the same (or roughly same) num ber of objects in each leaf node, which often result in that the distribution of the leaf nodes can not reflect the actual distribution of the objects. The description, analysis and experiments in this paper are based on R*-tree, a famous member of R-tree family. Anyway, we believe that the main idea of our proposal in this study can also be used to improve some other members of R-tree family. Our new proposal is called Clustered R*-tree (denoted CR*-tree). The experimental result indicates that the CR*-tree has better NN search performance than R*-tree and packed R-trees.
Important Links:
Go Back
