NSBR^*-tree: Building and Retrieving

Yaokai Feng, Masaaki Kubo, Zaher Aghbari, Akifumi Makinouchi

Research output: Contribution to journalArticle


R-trees are a common indexing technique for multi-dimensional data and are widely used in spatial and multi-dimensional databases. Nearest neighbor search(called NN search)is very popular in multimedia database and spatial database. According to out investigation, for a given database, the degree of the leaf nodes clustering the objects is a great factor on the NN searching performance. For R-trees, the objects are not well-clustered by its leaf nodes. Some packing algorithms for R-trees have been proposed. However, in these packing algorithms, the distribution of objects in its leaf nodes may not reflect the actual situation of objects and can not lead to a good clustering. An attempt combining clustering technology and R-trees(called SOM-based R^*-tree)is proposed by K.Oh and Y.Feng et al., which tries to decrease the number of objects in R-trees by building R-trees using the representative feature vectors of clusters instead of objects themselves. In the present paper, a new structure called NSBR^*-tree is proposed. The experimental result shows that the NSBR^*-tree has a much better searching performance.
Original languageEnglish
Pages (from-to)375-382
Number of pages8
JournalIPSJ SIG Notes
Issue number1
Publication statusPublished - Jul 17 2001


Dive into the research topics of 'NSBR^*-tree: Building and Retrieving'. Together they form a unique fingerprint.

Cite this