EFANNA 这篇文章我本来不是很想读，一来太老，二来性能也不是特别出色。但是看到 nsg 代码库使用 efanna 来初始化得到 KNN graph，所以还是捡起来看了看。
# 作者的动机
EFANNA 最大的创新点在于它同时使用了 KD-Tree 和 Graph 两种数据结构，KD-Tree 作为辅助数据结构可以更好地帮助 KNN graph 的构建和后续的查询。作者提出 EFANNA 的动机就是希望能同时使用到 tree 和 graph 两种数据结构的优点。这种辅助数据结构值得思考。
# 算法拆解
# 树构建算法
和传统的 KD-tree 最大的不同就是它的叶子结点中包含多个 point。
# initial graph
KGraph 中使用的是 random graph 作为初始图，然后使用 NN-descent 来进行图优化，作者的创新点在于它使用 KD-graph 来构建初始图。这里的算法挺抽象的，但是也很有意思。关键理解的点在于逐层 merge 思想。
来看这张图，对于查询点 q，这个 tree 最终导向节点 8。但是仅仅有节点 8 是不够的，从上面的图中可以看到节点 9 和节点 10 也离查询点比较近，于是我们需要 merge。merge 的思路就是从下往上。对于 level 2 来说，4 ➡️9 这个方向没有查，于是查 4->9，得到 9 节点，把节点 9 加入 candidate。对于 level 1 来说，2->5 这个方向没有查，于是用 q 查询，得到 10 节点，把节点 10 加入 candidate。对于 level 0 来说，1->3 这个方向没有查，查询得到节点 12，把节点 12 加入 candidate。这就是逐层 merge 的思想，当然实际中我们只会 merge 到一定层不会 merge 到 root。
# graph refine
这里它的算法我压根看不懂，然而作者来说他重写了 NN-Descent 为了更好地理解。总而言之，这里的 refine 算法就是 NN-descent。
# 查询算法
特点在于使用 KD-tree 来初始化 candidate：
