一种基于影响区域的CBRkNN查询方法
CBRkNN:an Influence zone based bichromatic reverse k nearest neighbor combined query method作者机构:杭州电子科技大学计算机学院浙江杭州310018 中国工商银行股份有限公司浙江杭州310000
出 版 物:《浙江大学学报(工学版)》 (Journal of Zhejiang University:Engineering Science)
年 卷 期:2014年第48卷第6期
页 面:1034-1042,1057页
核心收录:
学科分类:0810[工学-信息与通信工程] 08[工学] 081203[工学-计算机应用技术] 0805[工学-材料科学与工程(可授工学、理学学位)] 0812[工学-计算机科学与技术(可授工学、理学学位)]
基 金:国家自然科学基金资助项目(61003195 61070212 61100194 Y201120356)
摘 要:针对以集合点为发起者的双色反向k最近邻(BRkNN)查询效率问题,提出一种联合查询方法.BRkNN查询查找的是以查询点为k最近邻的点集,双色反向k最近邻联合(CBRkNN)查询查找的是以查询集合中某一设施集合为k最近邻的点集.该方法通过构造查询集合的影响区域来处理CBRkNN查询问题,任何一个物体落入影响区域就是查询结果,反之则不属于查询结果.算法通过画出用户感兴趣设施集合和用户不感兴趣设施集合之间的所有垂直平分线,计算集合中每个设施的优势支配区域,找出被优势支配区域覆盖个数小于k次的凸多边形区域以构造影响区域.在此基础上算法对影响区域进行点包含性查询得到最终结果.通过实验验证了算法在不同的用户规模、用户感兴趣/不感兴趣设施规模和不同的k值条件下都具有较小的时间消耗,从而说明影响区域的使用可以提高查询方法的有效性.