ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2020, Vol. 57 ›› Issue (6): 1335-1346.doi: 10.7544/issn1000-1239.2020.20190470

Previous Articles    

Reverse Nearest Neighbor Query Based on New Index Structure

Liu Runtao1,2, Liang Jianchuang1   

  1. 1(College of Science, Harbin University of Science and Technology, Harbin 150080);2(Institute of Information and Scientific Computing Technology, Harbin University of Science and Technology, Harbin 150080)
  • Online:2020-06-01
  • Supported by: 
    This work was supported by the National Natural Science Foundation of China (11871181).

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

CLC Number: