我有5000个维度的2000分，我想得到最近的邻居 .
现在我有一些问题，任何人都可以给出答案 .
-
人们说，它在高维度上运作良好 . 什么是时间复杂性？
-
@param max_nn_chks search is cut off after examining this many tree entries
在我读完算法之后，我想知道当我将max_nn_chks设置得太低时我是否会得到错误的答案 . 如果是的话，那就告诉我如何设置这个参数，否则给出一个理由，谢谢 .
- kdtree是我的数据获得最近邻居的最佳数据结构吗？
1 回答
时间复杂度与受限制的KD-Tree搜索基本相同，加上一些时间来维护优先级队列 . 受限制的KD树搜索算法需要以其全部深度（点计数的log2）乘以限制（允许访问的叶节点/点的最大数量）遍历树 .
是的，如果限制太低，你会得到一个错误的答案 . 您只能测量找到的真实NN的分数与搜索的叶子节点数 . 由此，您可以确定最佳值 .
通常，随机kd树林和分层k-means树表现最佳 . FLANN提供了一种方法来确定使用哪种算法（k-means与随机kd-tree林）并为您设置最佳参数 .
数据结构也有很大影响 . 例如，如果您知道有多个点集合在一起，则可以将它们分组到树的单个节点中（例如，通过它们的质心表示它们）并加快搜索速度 .
可以在数据上采用诸如视觉词，PCA或随机投影的另一种技术 . 这是一个非常活跃的研究领域 .