algorithm - 寻找 KD 树中所有节点的 KNN 的有效方法

Question

我目前正在尝试找到平衡 KD 树(K=2)的所有节点的 K 个最近邻居。

我的实现是 Wikipedia article 中代码的变体并且找到任何节点的 KNN 都非常快 O(log N)。

问题在于我需要找到每个节点的 KNN。如果我遍历每个节点并执行搜索，则需要大约 O(N log N)。

有没有更有效的方法来做到这一点？

Answer 1

根据您的需要，您可能想要尝试使用近似技术。详情请查看Arya and Mount关于这个主题的工作。一篇关键论文是here . BigO 复杂性详细信息位于其 '98 paper 中。 .

工作的图形说明如下所示:

^{来源:http://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif}

我在具有数十万个元素的超高维数据集上使用了他们的库。它比我发现的任何其他东西都快。该库处理精确和近似搜索。该软件包包含一些 CLI 实用程序，您可以使用它们轻松地试验您的数据集；甚至可视化 kd 树(见上文)。

FWIW:我使用了 R Bindings .

来自 ANN 的手册:

...it has been shown by Arya and Mount [AM93b] and Arya, et al. [AMN+98] that if the user is willing to tolerate a small amount of error in the search (returning a point that may not be the nearest neighbor, but is not significantly further away from the query point than the true nearest neighbor) then it is possible to achieve significant improvements in run- ning time. ANN is a system for answering nearest neighbor queries both exactly and approximately.