HCNNG (Hierarchical Clustering-Based Nearest Neighbor Graph)是近些年在多个benchmark中评测位列前茅的图索引，在许多数据集上性能优于HNSW，在部分生产环境中也有使用。其核心思想是通过多次合并局部最小生成树解决树索引的boundary issue，提高图的近邻连通性，最终提升查询性能。虽然是一个图索引的方法，在原理上却和random forest相近。

1. 索引构建

1.1 主图构建

• HCNNG是无向图。
• HCNNG会构建m个图，最终把这些图直接merge起来。
• 每个图是针对全量数据集层次化构建的，给定一个cluster最小的size n，构建图首先随机选择两个锚点，然后将其他点基于到锚点的距离进行就近分配。若分配后cluster size < n，则停止分裂。否则继续递归此过程。
• 在cluster tree构建完成之后，在每个叶子结点构造最小生成树。HCNNG用了一种变形算法，可以使得最小生成树中每个点的度数不超过3。
• 最后，自底向上，将叶子结点的图（MST）逐层merge起来，到根节点就得到了全量数据集的一个图。
• 注意到这样构造的图中，不同cluster之间没有连接；而且由于聚类树的空间分区不会很准确，cluster内向量的近邻性不会很好。因此HCNNG采取的方法是随机化构建多个图，再将图merge起来。
• 由于每个图的分区方式有区别，所以merge的时候会引入长边连接（单个图的cluster中不相似的向量之间的连接）

1.2 邻居kd-tree

• HCNNG将图中每个向量的邻居集合用kd-tree组织起来，相当于划分了邻居所处的空间。
• 实际实现中往往只会实现一个一层kd-tree，因为邻居数量并不多，选择分割最均匀的维度。

2. 索引查询

1. 构建multiple kd-trees快速寻找一批质量还不错的入口点；
2. greedy search，但是不搜全部的邻居，只搜kd-tree叶节点中的邻居。