空间数据库中反最远邻查询方法

Efficient algorithm for reverse furthest neighbor in spatial databases

在欧式空间下反最远邻查询算法的研究已取得了很多成果,但反最远邻查询问题还未得到有效解决。本文提出一种反最远邻查询算法,有效地解决了反最远邻查询问题,查询算法采用了过滤-提炼的解决模型。在过滤阶段,提出了反远中垂线裁剪方法。该裁剪法是通过做中垂线来过滤不是查询点的反最远邻的点。在提炼阶段,提出了反远范围查询提炼方法。该提炼方法是通过判断对象点是否在设定的范围外来验证该点是否是查询点的反最远邻。最后通过实验验证了所提算法的有效性。

At present, the reverse furthest neighbor query algorithm research has made a lot of achievements in spatial databases. But the problem of reverse furthest neighbor query is not effectively resolved in spatial databases. In this paper, a new reverse k furthest neighbor query algorithm is proposed, which effectively solve the reverse k furthest neighbor query problem in spatial dat- abases. The filter-refining solution model is used in this algorithm. In the filter stage, the reverse furthest perpendicular bisector cutting method is put forward, which can filter these points that are not the reverse k furthest neighbor points through the perpen- dicular bisectors. And in the refining stage, the reverse furthest range-k refining method is proposed, which can verify the point by determining whether it is out of the range. The experimental results show that the proposed algorithm is effective and efficiency.