反向最远邻的有效过滤和查询算法

摘要

反向最远邻(RFN)是空间数据库理论与应用中的一类新问题.为了有效地处理数据集中给定点的RFN查询,利用提出的离散边界点及邻域区等概念得到用于判定RFN的候选集的相关性质和定理,并给出其过滤算法.在得到过滤的候选集基础上,提出了F-RFN查询算法.对算法的正确性、可终止性和时间复杂性进行了分析.实验表明采用过滤方式的F-RFN查询比未经过滤的RFN查询的PA效率平均提高约37%.