ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2017, Vol. 54 ›› Issue (4): 861-871.doi: 10.7544/issn1000-1239.2017.20151111

Previous Articles     Next Articles

Voronoi-Based Group Reverse k Nearest Neighbor Query in Obstructed Space

Zhang Liping1, Liu Lei1, Hao Xiaohong1, Li Song1, Hao Zhongxiao1,2   

  1. 1(School of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080); 2(School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001)
  • Online:2017-04-01

Abstract: In order to solve the problem that the existing methods can not deal with the group reverse k nearest neighbor (GRkNN) query in obstructed space, the group reverse k nearest neighbor query method (OGRkNN) in obstructed space based on Voronoi diagram is put forward. The method finds data points that take any point in the query objects set as one of their obstacle k nearest neighbors. In the practical application, OGRkNN query can be used to evaluate the influence of a group of query objects. According to the changes of the obstacle set, the OGRkNN query in static obstacle environment (STA_OGRkNN query) and the OGRkNN query in dynamic obstacle environment (DYN_OGRkNN query) are given. The STA_OGRkNN query method greatly reduces the number of non-candidates by the properties of Voronoi diagram in pruning stage, and reduces the searching ranges quickly, which improves query efficiency. It also improves the accuracy of the algorithm in refining stage. Then three DYN_OGRkNN query algorithms are given. They are the OGRkNN query algorithm under the condition of dynamically increasing obstacles, the OGRkNN query algorithm under the condition of dynamically reducing obstacles and the OGRkNN query algorithm under the condition of dynamically moving obstacles. Theoretical study and experiments show that the proposed algorithms have extremely high efficiency.

Key words: Voronoi diagram, group reverse k nearest neighbor (GRkNN), obstructed space, spatial database, dynamic query

CLC Number: