search - kd 树对于 kNN 搜索是否有效。k 最近邻搜索

Question

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

但问题是我的算法对于 k=1 非常快，但对于 k>1 (k=2,5,10,20,100) 慢 2000 倍

这对 kd 树来说是正常的，还是我在做一些磨损的事情？

Answer 1

好吧，这主要取决于您的特定实现和数据集。

一个不平衡的树意味着你必须搜索比你需要的更多的数据。确保你的树结构是健全的。

它还可能取决于您如何找到 k 个邻居。如果您的算法在树中搜索最近的邻居并将其存储，然后搜索第二近的邻居并将其存储等等，那么您的搜索效率就不会很高。而是保留 k 个最近邻居的运行列表，并在您找到更接近的遍历树时将凹凸点排除在列表之外。这样你搜索一次，而不是 k 次。

不管怎样，听起来你是在为一门课程做这件事。尝试与您的教授、助教或同学交谈，看看您的结果是否典型。

Answer 2

我知道这个问题已得到解答，但有关使用 kd 树进行 KNN 搜索的更多详细信息，请参阅 Bentley (1975:514)，Communications of the ACM 18(9)，9 月。