search - 如何在欧几里得空间中找到最远的邻居？

Question

给定 2D 中 n 个点的集合 P，对于 P 中的任何点 x，找出 x 最远邻居的最快方法是什么？最远邻居是指 P 中与 x 具有最大欧几里德距离的点。

Answer 1

据我所知，当前针对各种树(R-Trees、quadtrees、kd-trees)的标准 kNN 搜索算法是由以下人员开发的:

G. R. Hjaltason and H. Samet., "Distance browsing in spatial databases.", ACM TODS 24(2):265--318. 1999

见 here .它基于最近节点/条目的优先级队列遍历树。 一个关键的见解是该算法也适用于最远邻居搜索 .

基本算法使用优先级队列。队列可以包含树节点以及数据条目，所有这些都按它们到搜索点的距离排序。
作为初始步骤，它将根节点添加到优先级队列。然后重复以下直到 k已找到条目:

从队列中取出第一个元素。如果是条目，则返回。如果是节点，则将该节点中的所有元素加入优先级队列。

重复 1。

该论文描述了 R-Trees 的实现，但他们声称它可以应用于大多数树状结构。我已经实现了 最近 我自己的邻居版本 R-Trees和 PH-Trees (一种特殊类型的四叉树)，均在 Java 中。我想我知道如何有效地为 KD-Trees 做到这一点，但我相信它有点复杂。