algorithm - 二维快速k-最近邻搜索的数据结构和算法的合适选择

Question

我有一个大约 100,000 (X, Y) 对表示二维空间中的点的数据集。对于每个 点，我想找到它的 k 个最近邻居。

所以，我的问题是 - 假设我想绝对减少整体运行时间，哪种数据结构/算法是合适的选择？

我不是在寻找代码 - 只是指向合适方法的指针。我对看似相关的选择范围感到有点畏惧 - 四叉树、R 树、kd 树等。

我认为最好的方法是构建一个数据结构，然后对每个点运行某种 k 最近邻搜索。但是，由于 (a) 我事先知道这些点，并且 (b) 我知道我必须对每个点都运行一次搜索，也许有更好的方法？

一些额外的细节:

• 因为我想尽量减少整个运行时间，所以我不关心大部分时间是花在结构上还是花在搜索上。
• (X, Y) 对分布得相当好，因此我们可以假设分布几乎均匀。

Answer 1

如果 k 相对较小(<20 左右)并且您的分布大致均匀，则创建一个覆盖点所在范围的网格，选择该网格以使每个网格的平均点数高于 k(这样一个位于中心的点通常会在那个网格点中得到它的 k 个邻居)。然后创建一组其他网格，沿每个轴从第一个(重叠)设置一半。现在对于每个点，计算它落入哪个网格元素(因为网格是规则的，不需要搜索)并从四个(或您拥有的许多重叠网格)中选择那个点最接近其中心的元素。

在每个网格元素中，点应按一个坐标(假设为 x)排序。从您选择的元素开始(使用二分法找到它)，沿着排序列表向外走，直到找到 k 个项目(同样，如果 k 很小，维护 k 个最佳命中列表的最快方法是使用二进制插入排序，当你插入时让最差的匹配项从末尾掉下来；插入排序通常在现代硬件上击败其他所有大约 30 个项目)。继续前进，直到你最远的最近邻居比 x 中离你最近的点离你更近(即不计算它们的 y 偏移量，所以可能没有比目前发现的第 k 个最近的点更近的新点) .

如果您还没有 k 个点，或者您有 k 个点但网格元素的一个或多个墙比 k 个点中最远的点更靠近您的兴趣点，请将相关的相邻网格元素添加到搜索中.

这应该会给你类似 O(N*k^2) 的性能，并且常数因子相对较低。如果 k 很大，那么这个策略就太简单了，你应该选择一个对 k 是线性或对数线性的算法，比如 kd 树。