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