k-d树是否有效用于kNN搜索。 k最近邻居搜索

Question

我必须实现k个最近邻居搜索kd-tree中的10维数据。

但问题是，我的算法是非常快的，其中k = 1，但高达2000倍慢对于k> 1（K = 2,5,10,20,100）

这是正常的KD树，还是我在做一些事情？

Answer 1

那么，它主要取决于你的特定实现和数据集。

平衡性差的树意味着您必须搜索比您需要的更多数据。确保你的树木结构健全。

它也可能取决于你如何找到k个邻居。如果你的算法搜索最近邻居的树并存储它，然后搜索第二个最近的邻居并存储它等，那么你不会非常有效地进行搜索。相反，当您找到更近的遍历树的列表时，请将列表中的k个最近邻居列表和碰撞点列表从列表中移出。这样你搜索一次，而不是k次。

无论哪种方式，这听起来像你这样做的课程。尝试与你的教授，助教或同学交谈，看看你的结果是否典型。

Answer 2

我知道这个问题已经回答了，但在KNN更详细的K-d树搜索，看到宾利（1975：514），在ACM 18（9），九月通信。