空间数据库中基于Voronoi图的组反k最近邻查询.pdf

ISSN 1673-9418 CODEN JKYTA8 E-mail: fcst@vip. 163.com Journal of Frontiers of Computer Science and Technology 1673-9418/2016/ 10(10)- 1365-11 Tel: +86-10 doi: 10.3778/j.issn. 1673-9418.1508004 空间数据库中基于Voronoi 图的组反k 最近邻查询* + 张丽平，刘 蕾，李 松，于嘉希 哈尔滨理工大学 计算机科学与技术学院，哈尔滨 150080 Group Reverse k Nearest Neighbor Query Based on Voronoi Diagram in Spatial Databases + ZHANG Liping , LIU Lei, LI Song, YU Jiaxi College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080, China + Corresponding author: E-mail: zhanglptg@ 163.com ZHANG Liping, LIU Lei, LI Song, et al. Group reverse k nearest neighbor query based on Voronoi diagram in spatial databases. Journal of Frontiers of Computer Science and Technology, 2016, 10(10) ：1365-1375. Abstract: To overcome the limitation of query objects in group reverse k nearest neighbor (GRkNN) query, this paper proposes the group reverse k nearest neighbor query method based on Voronoi diagram (V_GRkNN). The proposed method finds data points that take any point in the query objects set as one of their k nearest neighbors. In the practi- cal application, V_GRkNN query can be used to evaluate the influence of a group of query objects. Firstly, the query points set Q is optimized in order to reduce the effect of the query points number on query efficiency, the data points set P is pruned to reduce the searching ranges. And then according to the pruning strategies based on Voronoi dia- gram, the candidate set is filtered. Finally, a refinement process is used to get the query s final results. The V_GRkNN