查找KD树中所有节点的KNN的有效方法

Question

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

我的实现是来自维基百科文章的代码的变体,并且找到任何节点O(log N)的 KNN都非常快.

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

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

Answer 1

根据您的需要,您可能希望尝试近似技术.有关详细信息,请查看Arya和Mount关于此主题的工作.这里有一篇关键论文.BigO复杂性细节位于他们的'98论文中.

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

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

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

FWIW:我使用了R Bindings.

来自ANN的手册:

...... Arya和Mount [AM93b]和Arya等人已经证明了这一点.[AMN + 98]如果用户愿意容忍搜索中的少量错误(返回可能不是最近邻居的点,但距离查询点不比真正的最近邻居更远)那么可以显着改善运行时间.ANN是用于准确和近似地回答最近邻居查询的系统.