KDTree
KDTree的问题
KDTree的方法对于低维度近邻搜索非常快, 当D增长到很大时, 效率快速变低. 因为需要构建一个非常深的树, 并且每次回溯都要回溯非常多的节点.
因为对于高维向量, 单个维度对两个向量整体的距离是影响较小的, 因此与最初搜索到的叶子节点形成的超球面, 大概率会与很多超平面有交集, 因此回溯的次数会随着维度的增加快速增加.
一般来说, 要在维度D的数据集上取得较高的搜索效率, 要求数据集中数据的数量N要满足. 或使用KDBall来代替.
参考资料
最后更新于