Please wait a minute...
浙江大学学报(工学版)
计算机科学技术     
一种基于影响区域的CBRkNN查询方法
俞恒舟1,2, 任一支1, 徐建1, 徐明1, 郑宁1
1.杭州电子科技大学 计算机学院,浙江 杭州310018;2.中国工商银行股份有限公司,浙江 杭州310000
an Influence zone based bichromatic reverse k nearest neighbor combined query method
YU Heng-zhou1, 2, REN Yi-zhi1, XU Jian1, XU Ming1, ZHENG Ning1
1. College of Computer, Hangzhou Dianzi University, Hangzhou 310018, China;2. Industrial Commercial Bank of China Ltd, Hangzhou 310015, China
 全文: PDF(2441 KB)   HTML
摘要:

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

Abstract:

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 k, 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.

出版日期: 2015-04-01
:  TP 391  
基金资助:

 国家自然科学基金资助项目(61003195,61070212,61100194, Y201120356).

通讯作者: 徐建,男,副教授.     E-mail: jian.xu@hdu.edu.cn
作者简介: 俞恒舟(1987—),男,硕士生,从事空间数据库研究.E-mail: yuhz@sdc.icbc.com.cn
服务  
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章  

引用本文:

俞恒舟, 任一支, 徐建, 徐明, 郑宁. 一种基于影响区域的CBRkNN查询方法[J]. 浙江大学学报(工学版), 10.3785/j.issn.1008-973X.2014.06.010.

YU Heng-zhou, REN Yi-zhi, XU Jian, XU Ming, ZHENG Ning. an Influence zone based bichromatic reverse k nearest neighbor combined query method. JOURNAL OF ZHEJIANG UNIVERSITY (ENGINEERING SCIENCE), 10.3785/j.issn.1008-973X.2014.06.010.

链接本文:

http://www.zjujournals.com/eng/CN/10.3785/j.issn.1008-973X.2014.06.010        http://www.zjujournals.com/eng/CN/Y2014/V48/I6/1034

[1] 郭薇,郭菁,胡志勇.空间数据库索引技术[M].上海:上海交通大学出版社, 2006: 17.
[2] 曹泽文,谭川豫,王晓辉.移动对象反向最近邻查询处理技术研究进展[J].计算机工程与应用, 2011, 47(10): 138-141.
CAO Ze-wen,TAN Chuan-yu,WANG Xiao-hui. Review on techniques for reverse nearest neighbor query processing ofmoving objects[J].Computer Engineering and Applications, 2011, 47(10): 138-141.
[3] KORN F, MUTHUKRISHNAN S. Influence sets based on reverse nearest neighbor queries[C]∥Proceedings of SIGMOD Conference on Management of Data. New York: ACM, 2000: 201-212.
[4] YANG C, LIN K I. An index structure for improving closest pairs and related join queries in spatial databases[C]∥Proceedings of the International Data Engineering and Application Symposium. Los Alamitos: IEEE,2002: 352-362.
[5] STANOI I, AGRAWAL I, ABBADI AE. Reverse nearest neighbor queries for dynamic databases[C]∥Proceedings of ACM SIGMOD Workshop. Dallas: ACM, 2000: 744-755.
[6] TAO Y F, PAPADIAS D, LIAN X. Reverse kNN search in arbitrary dimensionality[C]∥Proceedings of VLDB Conference. Toronto: Morgan Kaufmann, 2004: 744-755.
[7] GAO Y J, ZHENG B H, CHEN G C, et al. Visible reverse k nearest neighbor query processing in spatial databases [J]. IEEE Transactions on Knowledge and Data Engineering, 2009, 21(9): 1314-1327.
[8] 杨泽雪,郝忠孝.空间数据库中的障碍反向最近邻查询[J].计算机工程与应用, 2011, 47(34): 130-133.
YANG Ze-xue,HAO Zhong-xiao.Obstructed reverse nearest neighbor queries in spatial databases[J].Computer Engineering and Applications, 2011, 47(34): 130-133.
[9] WU W, YANG F, CHAN CY, et al. Finch: Evaluating reverse k nearest neighbor queries on location data [C]∥ Proceedings of VLDB. Auckland: VLDB Endowment, 2008: 0561067.
[10] TRAN Q T, TANIAR D, SAFAR M, et al. Bichromatic reverse nearest neighbor search in mobile systems [J]. IEEE Systems Journal, 2010, 4(2): 230-242.
[11] TANIAR D, SAFAR M, TRAN Q T, et al. Spatial network RNN queries in GIS [J]. The Computer Journal, 2011, 54(4): 617-627.
[12] CHEEMA M A, LIN X M, ZHANG W J, et al. Influence zone: Efficiently processing reverse k nearest neighbors queries[C]∥Proceedings of ICDE. Hannove: IEEE,2011: 577-588.
[13] CHEEMA M A, ZHANG W J, LIN X M, et al. Efficiently processing snapshot and continuous reverse k nearest neighbors queries [J]. The VLDB Journal, 2012, 21(5): 703-728.
[14]KANG J M, MOKBEL M F, SHEKHAR S, et al. Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors[C]∥ Proceedings of ICDE.  Istanbul :IEEE,2007: 806-815.
[15]WONG R C W, OZSU T,YU P S, et al. Efficient method for maximizing bichromatic reverse nearest neighbor[C]∥ Proceedings of VLDB. Lyon: VLDB Endowment, 2009: 1126-1137.

[1] 何雪军, 王进, 陆国栋, 刘振宇, 陈立, 金晶. 基于三角网切片及碰撞检测的工业机器人三维头像雕刻[J]. 浙江大学学报(工学版), 2017, 51(6): 1104-1110.
[2] 王桦, 韩同阳, 周可. 公安情报中基于关键图谱的群体发现算法[J]. 浙江大学学报(工学版), 2017, 51(6): 1173-1180.
[3] 尤海辉, 马增益, 唐义军, 王月兰, 郑林, 俞钟, 吉澄军. 循环流化床入炉垃圾热值软测量[J]. 浙江大学学报(工学版), 2017, 51(6): 1163-1172.
[4] 毕晓君, 王佳荟. 基于混合学习策略的教与学优化算法[J]. 浙江大学学报(工学版), 2017, 51(5): 1024-1031.
[5] 王亮, 於志文, 郭斌. 基于双层多粒度知识发现的移动轨迹预测模型[J]. 浙江大学学报(工学版), 2017, 51(4): 669-674.
[6] 廖苗, 赵于前, 曾业战, 黄忠朝, 张丙奎, 邹北骥. 基于支持向量机和椭圆拟合的细胞图像自动分割[J]. 浙江大学学报(工学版), 2017, 51(4): 722-728.
[7] 黄正宇, 蒋鑫龙, 刘军发, 陈益强, 谷洋. 基于融合特征的半监督流形约束定位方法[J]. 浙江大学学报(工学版), 2017, 51(4): 655-662.
[8] 蒋鑫龙, 陈益强, 刘军发, 忽丽莎, 沈建飞. 面向自闭症患者社交距离认知的可穿戴系统[J]. 浙江大学学报(工学版), 2017, 51(4): 637-647.
[9] 穆晶晶, 赵昕玥, 何再兴, 张树有. 基于凹凸变换与圆周拟合的重叠气泡轮廓重构[J]. 浙江大学学报(工学版), 2017, 51(4): 714-721.
[10] 戴彩艳, 陈崚, 李斌, 陈伯伦. 复杂网络中的抽样链接预测[J]. 浙江大学学报(工学版), 2017, 51(3): 554-561.
[11] 刘磊, 杨鹏, 刘作军. 采用多核相关向量机的人体步态识别[J]. 浙江大学学报(工学版), 2017, 51(3): 562-571.
[12] 郭梦丽, 达飞鹏, 邓星, 盖绍彦. 基于关键点和局部特征的三维人脸识别[J]. 浙江大学学报(工学版), 2017, 51(3): 584-589.
[13] 王海军, 葛红娟, 张圣燕. 基于核协同表示的快速目标跟踪算法[J]. 浙江大学学报(工学版), 2017, 51(2): 399-407.
[14] 张亚楠, 陈德运, 王莹洁, 刘宇鹏. 基于增量图形模式匹配的动态冷启动推荐方法[J]. 浙江大学学报(工学版), 2017, 51(2): 408-415.
[15] 刘宇鹏, 乔秀明, 赵石磊, 马春光. 统计机器翻译中大规模特征的深度融合[J]. 浙江大学学报(工学版), 2017, 51(1): 46-56.