利用离散边界点判断的反向最远邻查询算法

计算机工程与科学

利用离散边界点判断的反向最远邻查询算法

杨秀娟1，宋俊山2，董军1，王丽芬1

（1.黑龙江科技大学计算机与信息工程学院，黑龙江哈尔滨 150022；2.大庆金桥信息技术工程有限公司，黑龙江大庆 163311）

收稿日期:2015-03-20 修回日期:2015-08-19 出版日期:2016-08-25 发布日期:2016-08-25
基金资助:
黑龙江省教育厅科学技术研究项目（12541731）

A reverse furthest neighbor query algorithm using discrete boundary points for judgment

YANG Xiu-juan1,SONG Jun-shan2,DONG Jun1,WANG Li-fen1

（1.College of Computer and Information Engineering,Heilongjiang University of Science and Technology,Harbin 150022;
2.Daqing Sunbridge Information Technology Engineering Co.,Ltd.,Daqing 163311,China）

Received:2015-03-20 Revised:2015-08-19 Online:2016-08-25 Published:2016-08-25

摘要/Abstract

摘要：

目前大部分的反向最远邻查询方法对查询点是否存在反向最远邻的情况不进行判断，当查询点不存在反向最远邻的结果集时，也进行全部的操作，增加了查询消耗。针对这种情况，提出了利用离散边界点判断查询点是否存在反向最远邻结果集的方法，利用离散边界点、四分邻域区和半平面修剪策略进行过滤操作，并验证过滤后得到的结果集中数据点的有效性。实验测试了查询点的位置对查询的影响和数据集的大小以及数据分布对查询的影响，并与利用凸包判断的方法进行了对比分析。实验结果表明，当查询点不是离散边界点时，查询消耗几乎为0，当查询点移动到边界时，查询消耗增加。实验表明提出的方法可以得到查询点的反向最远邻结果集。

关键词: 空间数据库, 反向最远邻查询, 离散边界点, 半平面修剪策略, 四分邻域区

Abstract:

At present, most of reverse furthest neighbor (RFN) query methods do not judge whether the query point has a result set, so even when a RFN result set does not exist, all the operations are still done and time is vainly consumed. To effectively deal with the RFN query problems, we propose a method in which whether the query point having a RFN result set is judged by discrete boundary points. Discrete boundary points, four neighborhood areas and half space trimming strategy are employed to do the filtering, and then the result set obtained by the filtering is verified. The impact of the position of the query point, the size of data sets and data distribution on queries is tested, which is also compared with that of the judging method using convex. Experimental results show that when the query point is not a discrete boundary point, the time consumption for queries is almost zero; but when the query point is a discrete boundary point, the time consumption increases, which demonstrates that the proposed method is effective and can get the RFN results set.

Key words: spatial database, reverse furthest neighbors query, discrete boundary points, half-space trimming strategy, four neighborhood areas

杨秀娟1，宋俊山2，董军1，王丽芬1. 利用离散边界点判断的反向最远邻查询算法[J]. 计算机工程与科学.

YANG Xiu-juan1,SONG Jun-shan2,DONG Jun1,WANG Li-fen1. A reverse furthest neighbor query algorithm using discrete boundary points for judgment [J]. Computer Engineering & Science.

参考文献

［1］Korn F, Muthukrishnan S. Influence sets based on reverse nearest neighbor queries［C］∥Proc of 2000 ACM SIGMOD International Conference on Management of Data,2000:201-212.
［2］Kang J,Mokbel M,Shekhar S,et al.Continuous evaluation of monochromatic and bichromatic reverse nearest neighbors［C］∥Proc of IEEE the 23rd International Conference,2007:806-815.
［3］Cheong O,Vigneron A,Yon J.Reverse nearest neighbor queries in fixed dimension［J］.International Journal of Computational Geometry & Applications,2011,21(2):179-188.
［4］Tao Y,Papadias D,Lian X.Reverse kNN search in arbitrary dimensionality［C］∥Proc of the 30th International Conference on Very Large Data Bases, 2004:744-755.
［5］Tran Q,Taniar D,Safar M.Bichromatic reverse nearest neighbor search in mobile systems［J］. Systems Journal IEEE,2010,4(2):230-242.
［6］Yao B,Li F,Kumar P.Reverse furthest neighbors in spatial databases［C］∥Proc of the 25th IEEE International Conference on Data Engineering,2009:664-675.
［7］Liu J,Chen H,Furuse K,et al.An efficient algorithm for reverse furthest neighbors query with metric index［C］∥ Proc of the 21st International Conference on Database and Expert Systems Applications,2010:437-451.
［8］Li Bo-han,Hao Zhong-xiao.Efficient filtration and query algorithm of reverse furthest neighbor ［J］.Journal of Chinese Computer Systems,2009,30(10): 1948-1951.(in Chinese)
［9］Liu J,Chen H,Furuse K,et al.An efficient algorithm for arbitrary reverse furthest neighbor queries［C］∥Proc of the 14th Asia-Pacific Web Conference,2012:60-72.
［10］Tran Q T,Taniar D,Safar M.Reverse nearest neighbor and reverse farthest neighbor search on spatial networks ［M］∥Transactions on Large Scale Data and Knowledge Centered Systems. Berlin:Springer Berlin Heidelberg, 2009:353-372.
［11］Wang Bao-wen, Peng Chuan, Chen Zi-jun, et al. Efficient algorithm for monochromatic and bichromatic reverse k furthest neighbor in road networks ［J］.Computer Engineering and Design,2012,33(8): 3099-3104.(in Chinese)
［12］Deng Cheng-yu,Peng Chuan,Wang Bao-wen,et al.Efficient algorithm for reverse k furthest neighbor in spatial databases ［J］.Journal of Yanshan University,2013,37(5): 412-419.(in Chinese)
［13］Yang Xiu-juan,Dong Jun,Li Hui-hui.Research of reverse furthest neighbors query in Euclidean space［J］.Computer Engineering and Applications,2015,51(4): 142-147.(in Chinese)
附中文参考文献：
［8］李博涵,郝忠孝.反向最远邻的有效过滤和查询算法［J］.小型微型计算机系统,2009,30（10）:1948-1951.
［11］王宝文,彭川,陈子军,等.路网上的单色和双色反k最远邻查询［J］.计算机工程与设计,2012,33（8）:3099-3104.
［12］邓成玉,彭川,王宝文,等.空间数据库中反k最远邻查询方法［J］.燕山大学学报,2013,37（5）:412-419.
［13］杨秀娟,董军,李慧慧.欧式空间中反向最远邻查询方法的研究［J］.计算机工程与应用,2015,51（4）:142-147.

[1]	董元张时忠. Oracle Spatial＆ Map Viewer在汽车导航定位上的应用[J]. J4, 2008, 30(6): 119-120.
[2]	赵珏[1,2] 康志伟[3]. WebGIS在税务管理系统中的应用[J]. J4, 2006, 28(9): 109-111.
[3]	卢炎生向祥兵潘鹏. CQRtree空间数据库索引结构及实现算法[J]. J4, 2006, 28(6): 108-111.
[4]	卢炎生杨攀宇潘鹏. 时空数据库事务并发控制的动态封锁[J]. J4, 2005, 27(5): 45-47.
[5]	于大东钟志农李军. 基于Oracle Spatial与GML的WebGIS研究[J]. J4, 2004, 26(4): 66-69.