I'm currently attempting to find K Nearest Neighbor of all nodes of a balanced KD-Tree (with K=2).
My implementation is a variation of the code from the Wikipedia article and it's decently fast to find KNN of any node O(log N).
The problem lies with the fact that I need to find KNN of each node. Coming up with about O(N log N) if I iterate over each node and perform the search.
Is there a more efficient way to do this?
根据您的需要，您可能希望尝试使用近似技术。有关详细信息，请查看Arya 和 Mount在该主题上的工作。关键文件在这里。BigO 复杂性详细信息位于他们的'98 论文中。
该工作的图形说明如下所示：
来源：http ://www.cs.umd.edu/~mount/ANN/Images/annspeckle.gif
我已经在具有数十万个元素的非常高维数据集上使用了他们的库。它比我发现的其他任何东西都快。该库处理精确搜索和近似搜索。该软件包包含一些 CLI 实用程序，您可以使用它们轻松地试验您的数据集；甚至可视化 kd-tree（见上文）。
FWIW：我使用了R 绑定。
来自ANN的手册：
... Arya 和 Mount [AM93b] 以及 Arya 等人已经证明了这一点。[AMN+98] 如果用户愿意容忍搜索中的少量错误（返回一个可能不是最近邻的点，但与真正的最近邻相比距离查询点的距离不远），那么可以显着改善运行时间。ANN 是一个准确和近似地回答最近邻查询的系统。
我使用覆盖树来解决这个问题。这是链接：http ://hunch.net/~jl/projects/cover_tree/cover_tree.html
在一个 50M 大小的数据集中（所有 kNN 查询，k=100），覆盖树创建耗时 5.5 秒，查询耗时 120 秒。Ann lib 创建树用了 3.3 秒，查询用了 138 秒。
更新：最近邻不是对称关系。考虑一下：A(0,0) B(1,0) C(3,0)。B 是 C 最接近的，而 C 不是 B 最接近的
如果节点本身是查询点，那么搜索时间可能会更短。您可以从回溯阶段开始，测试的第一个节点已经在查询点附近。然后可以很快修剪大面积的树。
最近邻居是对称关系（如果 n1 是 n2 的最近邻居，则同样适用于 n2），因此您只需搜索一半的节点，跳过所有已标记为最近邻居的节点。只是一个想法。
您也可以尝试 KD-Tree BBF（Best-Bin First）搜索，这将帮助您更快地搜索到最近的节点（bins）。我已经在 C# 中实现了这个，所以如果您对源代码感兴趣，请写信给我。
当然，实际运行时间取决于维度、KD-Tree 结构和数据集中点的分布。
点的聚类也可能是合适的。
要搜索的术语是knn join。更准确地说，您可能想要进行自联接。
也许这些搜索结果有帮助：
我只见过 R*-tree 的 knn 连接算法。但是，在我自己的实验中，它们无法胜过重复查询。我可能会遗漏一些实现想法。但总的来说，为树连接适当地保存数据比单个 knn 查询要棘手得多。
