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

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

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

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.