kdtree - kd-tree BBF算法时间复杂度

Question

我有 5000 个维度的 2000 个点，我想得到最近的邻居。

现在遇到了一些问题，谁能解答一下。

1. 人们说，它适用于高维度。时间复杂度是多少？

2. 在检查了这么多树条目后，@param max_nn_chks 搜索被切断

   在我阅读了算法之后，我想知道当我将 max_nn_chks 设置得太低时是否会得到错误的答案。如果是，请告诉我如何设置此参数，否则请说明原因，谢谢。

3. kdtree 是我的数据获取最近邻居的最佳数据结构吗？

Answer 1

1. 时间复杂度与受限 KD-Tree 搜索中的基本相同，加上一些维护优先级队列的时间。受限 KD-Tree 搜索算法需要遍历树的全深度（点计数的 log2）乘以限制（允许访问的叶节点/点的最大数量）。

2. 是的，如果限制太低，你会得到错误的答案。您只能测量找到的真实 NN 与搜索的叶节点数的比例。由此，您可以确定您的最佳价值。

3. 通常随机 kd-tree 森林和分层 k-means 树表现最好。FLANN提供了一种方法来确定使用哪种算法（k-means 与随机 kd-tree 森林）并为您设置最佳参数。

数据的结构也有很大的影响。例如，如果您知道有一些点簇靠近在一起，您可以将它们分组到树的单个节点中（例如，用它们的质心表示它们）并加快搜索速度。

可以对数据采用其他技术，例如视觉词、PCA 或随机投影。这是一个相当活跃的研究领域。