关键词: Voronoi图, 反k最近邻, 组反k最近邻, 索引结构

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 practical 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 diagram, the candidate set is filtered. Finally, a refinement process is used to get the query's final results. The V_GRkNN method greatly improves the query speed and efficiency. Theoretical research and experiments show that the efficiency of the proposed V_GRkNN method obviously outperforms other algorithms.

Key words: Voronoi diagram, reverse k nearest neighbor, group reverse k nearest neighbor, index structure