Computer Engineering and Applications ›› 2015, Vol. 51 ›› Issue (4): 142-147.

Previous Articles     Next Articles

Research of reverse furthest neighbors query in euclidean space

YANG Xiujuan1, DONG Jun1, LI Huihui2   

  1. 1.College of Computer and Information Engineering, Heilongjiang Institute of Science and Technology, Harbin 150022, China
    2.Department of Mechanical and Electrical Engineering Technology, Heilongjiang College of Construction, Harbin 150025, China
  • Online:2015-02-15 Published:2015-02-04


杨秀娟1,董  军1,李慧慧2   

  1. 1.黑龙江科技大学 计算机与信息工程学院,哈尔滨 150022
    2.黑龙江建筑职业技术学院 机电工程技术学院,哈尔滨 150025

Abstract: Most of the reverse furthest neighbor query algorithm based on filter-purification of query processing framework, the relationship between dataset and a query point is not to judge. To effectively deal with the reverse furthest neighbor query problem, a Euclidean space reverse furthest neighbor query method is given. First with inquiry judge the distance between the query point and the convex hull different conditions are obtained, and then filtering and purifying the two step process. In the filtering step, a large number of data points drop using half-space trimming strategy, in the purifying step, the data point which is not the reverse furthest neighbor of query point is excluded. Experimental results demonstrate that the effectiveness of the algorithm.

Key words: Euclidean space, furthest neighbors query, reverse furthest neighbors query, convex hull, half-space trimming strategy

摘要: 大部分反向最远邻查询算法采用过滤-提纯查询处理框架,对数据集和查询点的位置关系不进行判断。针对这种情况,提出了一种处理欧式空间中反向最远邻查询方法,首先利用查询点与凸包之间的位置关系进行判断,得到三种情况,针对第三种情况再进行过滤和提纯两步处理。在过滤步骤中,使用修改的半平面修剪策略,除去大量的数据点,在提纯步骤排除不是查询点反向最远邻的数据点。实验结果验证了算法的有效性。

关键词: 欧式空间, 最远邻查询, 反向最远邻查询, 凸包, 半平面修剪策略