Abstract: To improve the efficiency of reverse nearest neighbor query, firstly the definition of the minimum bounding square based on nearest neighbor distance (MBSD) for spatial data and the definitions of four orders for spatial data are given. Then a new spatial data index structure—the index tree based on the minimum bounding square and the distance of nearest neighbor(MBDNN-tree) is proposed according to these definitions. The new index structure uses the idea of dividing spatial data in the R-tree, to construct the nodes on each level of an MBDNN-tree according to nodes’ geometric distribution and the corresponding order relation of nodes, by dividing the original data set in defined orders from top to bottom, and from left to right by using its MBSD to represent data. And then the detailed description and proof analysis are made for the algorithms in the preprocessing and constructing procedures used for creating an MBDNN-tree. The properties of an MSDNN-tree are obtained. Then the pruning rules for reverse neighbor query on an MBDNN-tree are set up, and further the reverse neighbor query algorithm on an MBDNN-tree is presented. The geometric orders among the nodes on the same level of an MBDNN-tree are used to reduce the visited node number of an MBDNN-tree for the reverse neighbor query so that the algorithm’s query efficiency is greatly improved. Finally, the reverse nearest neighbor query algorithm based on this structure is analyzed experimentally. Experiments show that the reverse nearest neighbor query algorithm based on MBDNN- tree has better query performance.

Key words: MSDNN-tree, spatial database, index structure, reverse nearest neighbor, query algorithm