如何遍历 KDTree 找到 k 个最近的邻居？

Question

本题涉及KDTrees的KNN搜索实现。遍历 KDTree 以找到单个最佳匹配（最近邻）非常简单，类似于修改后的二进制搜索。

如何修改遍历以详尽有效地找到 k 个最佳匹配 (KNN)？

编辑澄清：在找到与输入查询I最近的节点M后，遍历算法如何继续寻找剩余的K-1个最接近查询的匹配？是否有一种遍历模式可以保证按照与查询的最佳匹配到最差匹配的顺序访问节点？

Answer 1

目前，我已经确定了 sub-optimal 解决方案，即执行一系列逐渐扩大范围的搜索，直到找到 K 个节点。

Answer 2

您可以维护一个大小为 k 的最大堆（k 是我们想要找到的最近邻居的数量）。

从根节点开始，在最大堆节点插入距离值。继续使用维度拆分、标准在 k-d 树中搜索并不断更新最大堆树。

https://gopalcdas.wordpress.com/2017/05/24/construction-of-k-d-tree-and-using-it-for-nearest-neighbour-search/

~阿希什

Answer 3

添加到@Ashish 的回答中，您可以按以下方式使用 max-heap：

1) Build a max-heap of the first k elements (arr[0] to arr[k-1]) of the given array.

这一步是O(k)。那么

2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with 
   root of the max-heap.
    a) If the element is smaller than the root then make it root 
       and call heapify for max-heap.
    b) Else ignore it.

第2步是O((n-k)*log(k)).

3) Finally, the max-heap has k smallest elements and root of the heap 
   is the kth smallest element.

时间复杂度：O(k + (n-k)*log(k)) 无排序输出。如果需要排序输出则 O(k + (n-k)*log(k) + k*log(k)).

如何遍历 KDTree 找到 k 个最近的邻居？

How do I traverse a KDTree to find k nearest neighbors?

nearest-neighbor

knn

kdtree