HNSW算法----hierarchcalnavigablesmallworldgraphs的第一贡献者： Y.Malkov (俄罗斯) )。
一.背景介绍NN最近邻搜索广泛应用于各类搜索、分类任务，在巨大的数据集上由于高效的原因转化为美丽的鼠标。 常见的算法是KD树、LSH、IVFPQ和文中提到的HNSW。
hnsw (hierarchicalnavigablesmallworld )是基于鼠标的美丽搜索区域的图表算法。 我们将d维空间的所有向量构筑成相互连接的图表，根据该图表检索某个顶点的k个最近邻
二.说起nswhNSW，不得不提到前作的NSW。 在nsw中，作者创建了一个名为Delaunay graph的类，在这里我们首先看了一下Delaunay graph。
Delaunay graph的构建过程如下。
1 .构造一个包含所有散布点的超级三角形，放入三角形链表2 .依次插入点集的散布点，在三角形链表中找出其外接圆包含插入点的三角形(称为此点的影响三角形)，删除影响三角形的公共边，将插入点与三角形完成一点向Delaunay三角形链表的插入3 )基于优化准则对局部新形成的三角形进行优化。 将形成的三角形放入Delaunay三角形链表4。 重复上述步骤2，直到插入所有散点
的Delaunay graph具有这些优点。 图中所有点都有“友点”，不存在“孤点”，搜索不到的近点都互相“友点”，保证了搜索结果的准确性； 图中所有链接(线段)的数量最少，保证了检索的效率。
但是，NSW没有用这种方式进行制图。 这是因为，这种作图方式在作图和搜索的时间上的复杂性太高了。 NSW的作图方式非常简单，在图中插入新点时，从随机存在的一个点到离新点最近的m个点，m由用户设定。 是连接新点和这个最近的m个点的over。
NSW论文中有这样的图。 黑色是连接附近点的线，红线是“高速公路的结构”。
我们从enter point点进入搜索，在寻找绿色点靠近节点的地方时，可以使用用红色连接的“高速公路机制”快速找到结果。
高速公路是怎么形成的呢？ 初期建设时，点还很少，因为此时连接的m个点可能在建设后期的中间增加了上千个点，所以建设初期连接的这些边自然变成了“高速公路”。
对于查询，这里有三个点的集合： candidates、visitedset和results。 在这里，candidates是现在考察的点的集合
visitedset是已经访问过的点的集合
results是当前离查询点最近的点的集合
头两个变长，最后是定长。
查询流程如下：
1 .随机选择一个点作为查询的起点entry_point，并将该点添加到candidates中。 同时添加可视化集2。 遍历candidates，从candidates中选择离查询点最近的点c，并将其与results中离查询点最远的点d进行比较。 如果C和查询点终止查询，则表示在当前图中找到了所有离查询点最近的点，或者candidates为空。 3 .从3.candidates中删除点c4。 查询c的所有邻居e，如果e已经存在于visitedset中，则跳过它，否则将其添加到visitedset5中。 将比d和q的距离更近的e添加到candida ated results满后，与q相距最远的点6 .循环2-5 论文中的伪码：
k-nnsearch(objectq，integer: m，k ) TreeSet [object] tempRes，candidates，visitedSet，result //)循环m次，随机性I ) do : putrandomentrypointincandidatestempresnull repeat : /使用上述贪婪搜索算法最接近q的点cgetelementcclosestfromcandidatestestestes 判断结束条件ifcisfurtherthank-thelementfromresultthenbreakrepeat /更新后选择列表foreveryelementefromfriendsofcdo : ifeisnotinvisitedseted candidates，tempRes end repeat //聚集结果addobjectsfromtemprestoresultendforreturnbestkel
ements from result 三. HNSWHNSW是对NSW的进一步优化，论文中的一张图足以解释HNSW做了什么改变：
1.第0层中包含图中所有节点
2.向上节点数依次减少，遵循指数衰减概率分布
3.建图时新加入的节点由指数衰减概率函数得出该点最高投影到第几层
4.从最高的投影层向下的层中该点均存在
5.搜索时从上向下依次查询
这里重点说一下增加节点：
输入:hnsw：q插入的目标图
q：插入的新元素
M：每个点需要与图中其他的点建立的连接数
Mmax：最大的连接数，超过则需要进行缩减
efConstruction：动态候选元素集合大小
mL：选择q的层数时用到的标准化因子
INSERT(hnsw, q, M, Mmax, efConstruction, mL)
1.先计算这个点可以深入到第几层，lßfloor(-ln(uniform(0,1)) * ml)
2.自顶层向q的层数l逼近搜索，一直到l+1,每层寻找当前层q最近邻的1个点
3.自l层向底层逼近搜索,每层寻找当前层q最近邻的efConstruction个点赋值到集合W
4.在W中选择q最近邻的M个点作为neighbors双向连接起来
5.检查每个neighbors的连接数，如果大于Mmax，则需要缩减连接到最近邻的Mmax个
6.在某一层中查询最近邻和NSW中的查询算法一致，这里就不重复了
需要注意的是第5点，每个节点的出度是有上限的，这样可以保证搜索的效率，这里就需要针对某些边进行裁剪，那么该裁剪哪些边呢？Fast Approximate Nearest Neighbour Graphs一文中给出了裁边的原则：
edge(p1, p2) occludes edge(p1, p3) if
d(p1, p2) < d(p1, p3) and d(p2, p3) < d(p1, p3)
用在这张图上，p1连接了p2、p3、p4，其中p1p3会被裁掉
github
self.index = hnswlib.Index(space = 'cosine', dim = self.dim) # possible options are l2, cosine or ipself.index.init_index(max_elements = num_elements, ef_construction = 200, M = 16)vectors = np.squeeze(np.array(self.vectors)).reshape((len(self.vectors), -1))# Element insertion (can be called several times):self.index.add_items(vectors, ids)# Controlling the recall by setting ef:self.index.set_ef(50) # ef should always be > kself.index.save_index(hnsw_path)self.index.load_index(hnsw_path, max_elements = num_elements)参考：
HNSW详解系列