一种基于影响区域的CBRkNN查询方法

CBRkNN:an Influence zone based bichromatic reverse k nearest neighbor combined query method

针对以集合点为发起者的双色反向k最近邻(BRkNN)查询效率问题,提出一种联合查询方法.BRkNN查询查找的是以查询点为k最近邻的点集,双色反向k最近邻联合(CBRkNN)查询查找的是以查询集合中某一设施集合为k最近邻的点集.该方法通过构造查询集合的影响区域来处理CBRkNN查询问题,任何一个物体落入影响区域就是查询结果,反之则不属于查询结果.算法通过画出用户感兴趣设施集合和用户不感兴趣设施集合之间的所有垂直平分线,计算集合中每个设施的优势支配区域,找出被优势支配区域覆盖个数小于k次的凸多边形区域以构造影响区域.在此基础上算法对影响区域进行点包含性查询得到最终结果.通过实验验证了算法在不同的用户规模、用户感兴趣/不感兴趣设施规模和不同的k值条件下都具有较小的时间消耗,从而说明影响区域的使用可以提高查询方法的有效性.

To improve the efficiency of bichromatic reverse k nearest neighbor （BRkNN） query from a set of query objects, this work proposed a new combined query method. Given a set of objects involving two types of data, a BRkNN query is issued by a query object from the first type of set and finds the objects in the second type whose k nearest neighbors in the first type of set include the query object; but a CBRkNN query is to find such objects result in the second type of set for a set of query objects in the first type of set. This work used the constructed influence zone of query set to resolve the CBRkNN query, i.e. any point inside the influence zone is the query results, and any point outside the influence zone does not belong to the query results. This algorithm draws all the perpendicular bisector between the interested points set and the uninterested points set, computes the dominating area of each point in the set, and uses the convex polygon areas whose covered number by the dominating area is less than te, to construct the influence zones; then the final result is obtained by the point inclusion query for the influence zones. The experimental results showed less time consumption than the existing algorithms under different user scales, the scale of the interesting objects set and the uninteresting objects sestet, and different k values. And the result indicates that using the influence zone can improve the effectiveness of query method.