标题：efanna:基于KNN-Graph的超快ANN算法
- 基本思路：在KNN-Graph上保留一个randomize kd-trees，作为KNN-Graph的入口点
- 搜索算法：
- 在randomize kd-trees上先搜索，每个tree平均分配限额，最终保留E个最近点做图的入口点；
- 在图上找这些入口点的邻居们，每一次迭代保留最近的P个，迭代I次，返回结果。
- 构建算法：通过randomize kd-trees优化nn-descent的初始化图
- 构建randomize kd-trees；
- 对于每一个数据集中的点q，以及每一个kd-tree，找到对应的target leaf，然后去找它的sibling（二叉kd-tree只有一个兄弟），然后在以sibling为根的子树上找到离q最近的leaf；以这样的方式向上每层找一个兄弟，直到一个给定层。
- 用找到的K个最近邻初始化KNN-Graph
-
NN-descent来迭代优化KNN-Graph
image.png
网友评论