HNSW算法----hierarchcalnavigablesmallworldgraphs，第一贡献者： Y.Malkov (俄罗斯)一.背景介绍在广阔的数据中进行高效的相似性搜索例如，如果我在sogou APP上读了一篇文章，推荐系统应该为我推送最接近这篇文章的文章。 数据库中的所有文章都用向量表示，所以我们要解决的问题是“找到与本文的向量最接近的几个向量”。 然后，推送与这些向量对应的文章。 数据库中的文章有千万篇，所有用户每秒都要求千万篇。 要解决这个问题，需要一种快速、准确、相对节约资源的方法。
解决这个问题的方法有很多。 PQ、Annoy、HNSW等。 由于篇幅有限，本文仅介绍HNSW算法。
二.朴素的想法
朴素的构思图
请看上图。 假设现在有13个二维数据向量。 将这些向量放在平面直角坐标系内，隐藏了坐标系的刻度。 它们的位置关系如上图所示。
朴素的搜索法：很多人在脑海里提出这样朴素的想法，把几个点之间在线连接起来，组成搜索图，存起来备用； 当我想找离粉色点最近的点时，我会计算任意黑点到粉色点的距离。 与该任意黑点有联系的点称为“友点”。 然后，计算这个黑点的所有“友点”和粉色点之间的距离，从所有的“友点”中选择离粉色点最近的点。 将此点作为下一个进入点如果当前黑点和粉红色点的距离比所有“友点”都近，则中止搜索。 这个黑点是离粉红色点最近的点。
如果你不明白上面的文字说明，就举个例子吧。 目标：找离粉红色点最近的点。 步骤：从其中一个黑点出发。 在这里，我随便选c点。 计算c点和粉红色点的距离，并储存起来。 然后计算c点的所有友点(a，I，b )和粉红色点的距离。 距离和测量方法有很多种，这里采用花痴的长颈鹿距离。 二维物理空间上的“近点和远点”。 计算B和B点的距离最近的点。B点和B点的距离保存，B点的友点为e、a、c、I、h，分别计算与B点的距离，e点和B点的距离最近，且e点比B点更接近B点。 e点的友点是j、b、d、g。 此时，得知与j点的粉红色点的距离是最近的。 但是，由于but、however、j点离粉红色点的距离比e点还远，因此满足搜索结束的条件，返回e点。
朴素的想法之所以被称为朴素的想法，是因为它的缺点很多。 首先，我发现图中的k点是无法检索的。 k点没有朋友，该怎么办？ 接下来，找离粉红色点最近的两个点。 如果这两个近点之间没有连接，则会严重影响效率。 例如，如果l和e的点、l和e有连接，就可以很容易地检测出离粉红色点最近的两个点。 我该怎么办？ 最后一个大问题是，D积分真的需要这么多“朋友积分”吗？ 应该怎么决定是谁的朋友？
对于k点问题，规定了构图时所有数据向量节点必须有友点。 关于l和e的问题，构图时一定程度上接近(相似)距离的所有向量必须相互是朋友点。 关于d点问题，考虑到构建该图表的时间复杂性，决定尽量减少各节点的“友点”数量。 带着这三条规定，我们进入下一章。
三.NSW算法图论中存在前一节所述朴素思想缺陷问题——具有很好的分割法则来解决粗暴的烟草(Delaunay )三角剖分算法，该算法可以达到以下要求。 1、图中各点均有“友点”。 2、相近的点彼此是“友点”。 3、图中所有链接(线段)的数量最少。 效果如下图所示。
但NSW采用粗暴的烟草三角剖分法并不构成粗暴的烟草三角网格图。 原因之一是粗鲁的烟草三角剖分构图算法时间复杂度太高，换句话说构图耗时太长。 其原因之二，粗暴的烟草三角形的搜索效率未必是最高的。 如果初始点和搜索点的距离很远，我们需要多次跳跃找到其邻近点。 高速公路“Expressway mechanism”，这里需要在一些远的点之间有线段的连接，以便能够快速搜索。 在理想情况下，我们的算法不仅要满足以上三个需要，而且具有低复杂度、具有高速公路机制的构图方法。
NSW论文中有这样的图。 黑色是连接附近点的线，红线是“高速公路的结构”。 我们从enter point点进入搜索，在寻找绿色点靠近节点的地方时，可以使用用红色连接的“高速公路机制”快速找到结果。
现在，当在图中每次插入一个点并在插图中插入全新点时，NSW朴素构图算法通过朴素概念中的朴素发现方法(通过计算“朋友点”与插入点之间的距离来确定下一个进入点是哪个点)来确定在该全新点上最接近的点糟了。
上面这是完蛋了
而止的算法描述中有些读者肯定会问，就这么简单？对，就这么简单。我们来理智地分析一下这个算法。首先，我们的构图算法是逐点随机插入的，这就意味着在图构建的早期，很有可能构建出“高速公路”。假设我们现在要构成10000个点组成的图，设置m=4（每个点至少有4个“友点”），这10000个点中有两个点，p和q，他们俩坐标完全一样。假设在插入过程中我们分别在第10次插入p，在第9999次插入q，请问p和q谁更容易具有“高速公路”？答：因为在第10次插入时，只见过前9个点，故只能在前9个点中选出距离最近的4个点（m=4）作为“友点”，而q的选择就多了，前9998个点都能选，所以q的“友点”更接近q，p的早期“友点”不一定接近p，所以p更容易具有“高速公路”。结论：一个点，越早插入就越容易形成与之相关的“高速公路”连接，越晚插入就越难形成与之相关的“高速公路”连接。所以这个算法设计的妙处就在于扔掉粗暴的香烟三角构图法，改用“无脑添加”（NSW朴素插入算法），降低了构图算法时间复杂度的同时还带来了数量有限的“高速公路”，加速了查找。下面对NSM朴素构图算法的过程举例，已经看懂上面文字描述的读者可以跳过下一段。
我们对7个二维点进行构图，用户设置m=3（每个点在插入时找3个紧邻友点）。首先初始点是A点（随机出来的），A点插入图中只有它自己，所以无法挑选“友点”。然后是B点，B点只有A点可选，所以连接BA，此为第1次构造。然后插入F点，F只有A和B可以选，所以连接FA，FB，此为第2此构造。然后插入了C点，同样地，C点只有A，B，F可选，连接CA，CB，CF，此为第3次构造。重点来了，然后插入了E点，E点在A，B，F，C中只能选择3个点（m=3）作为“友点”，根据我们前面讲规则，要选最近的三个，怎么确定最近呢？朴素查找！从A，B，C，F任意一点出发，计算出发点与E的距离和出发点的所有“友点”和E的距离，选出最近的一点作为新的出发点，如果选出的点就是出发点本身，那么看我们的m等于几，如果不够数，就继续找第二近的点或者第三近的点，本着不找重复点的原则，直到找到3个近点为止。由此，我们找到了E的三个近点，连接EA，EC，EF，此为第四次构造。第5次构造和第6次与E点的插入一模一样，都是在“现成”的图中查找到3个最近的节点作为“友点”，并做连接。
图画完了，请关注E点和A点的连线，如果我再这个图的基础上再插入6个点，这6个点有3个和E很近，有3个和A很近，那么距离E最近的3个点中没有A，距离A最近的3个点中也没有E，但因为A和E是构图早期添加的点，A和E有了连线，我们管这种连线叫“高速公路”，在查找时可以提高查找效率（当进入点为E，待查找距离A很近时，我们可以通过AE连线从E直接到达A，而不是一小步一小步分多次跳转到A）。
关于NSW算法的朴素构思就讲到这里了，下面我们来说说优化。
一.在查找的过程中，为了提高效率，我们可以建立一个废弃列表，在一次查找任务中遍历过的点不再遍历。在一次查找中，已经计算过这个点的所有友点距离查找点的距离，并且已经知道正确的跳转方向了，这些结果是唯一的，没有必要再去做走这个路径，因为这个路径会带给我们同样的重复结果，没有意义。
二.在查找过程中，为了提高准确度，我们可以建立一个动态列表，把距离查找点最近的n个点存储在表中，并行地对这n个点进行同时计算“友点”和待查找点的距离，在这些“友点”中选择n个点与动态列中的n个点进行并集操作，在并集中选出n个最近的友点，更新动态列表。
注意，插入过程之前会先进行查找，所以优化查找过程就是在优化插入过程。以下给出NSW查找步骤。设待查找q点的m个近邻点。
1.随机选一个点作为初始进入点，建立空废弃表g和动态列表c，g是变长的列表，c是定长为s的列表（s>m）,将初始点放入动态列表c（附上初始点和待查找q的距离信息），制作动态列表的影子列表c'。
2.对动态列表c中的所有点并行找出其“友点”，查看这些“友点”是否存储在废弃表g中，如果存在，则丢弃，如不存在，将这些 剩余“友点”记录在废弃列表g中（以免后续重复查找，走冤枉路）。
3.并行计算这些剩余“友点”距离待查找点q的距离，将这些点及其各自的距离信息放入c。
4.对动态列表c去重，然后按距离排序（升序），储存前s个点及其距离信息。
5.查看动态列表c和c'是否一样，如果一样，结束本次查找，返回动态列表中前m个结果。如果不一样，将c'的内容更新为c的 内容，执行第2步。
插入算法更简单了，插入算法就是先用查找算法查找到m个（用户设置）与待插入点最近的点，连接它们，完了。
以上就是NSW算法的全部内容，HNSW就是NSW再优化版本。如果你需要消化一下上面的内容，我建议你明天再看下面， 因为笔者也不是一天就撸懂了他的论文。为了搞懂这个算法，笔者总共撸了三篇论文，NSW是其中一本，另一本是HNSW，不 看NSW就看不懂HNSW，另外还撸了美丽的冬日多边形和粗暴的香烟三角剖分的化石级论文，然后Malkov先生在NSW论文某段中告诉我，它构造的“伪粗暴的香烟三角剖分图”和真粗暴的香烟三角剖分图没有任何关系，只是随便取了这个名罢了，我喝着水差点把我呛死。
四.跳表结构设有有序链表，名叫sorted_link，里面有n个节点，每个节点是一个整数。我们从表头开始查找，查找第t（0<t<n）个节点 需要跳转几次？答：t-1次（没错，我是从1开始数的）。把n个节点分成n次查找的需求，都查找一遍，需要跳转几次？答： （0+1+2+3+.....+（n-1））次。
如果我这链表长成下图这样呢？
这已经不是一个有序链表了，这是三个有序链表+分层连接指针构成的跳表了。看这张示意图就能明白它的查找过程，先查第一层，然后查第二层，然后查第三层，然后找到结果。如果把上段所描述的名字叫sorted_link的链表建立成这样的跳表，那么把sorted_link中的所有元素都查一遍还需要花费（0+1+2+3+.....+（n-1））次吗？当然不需要。那么具体是多少次呢？如果你真的关心，请搜狗搜索关键词“跳表”。
跳表怎么构建呢？三个字，抛硬币。对于sorted_link链表中的每个节点进行抛硬币，如抛正，则该节点进入上一层有序链 表，每个sorted_link中的节点有50%的概率进入上一层有序链表。将上一层有序链表中和sorted_link链表中相同的元素做一一对应的指针链接。再从sorted_link上一层链表中再抛硬币，sorted_link上一层链表中的节点有50%的可能进入最表层，相当于sorted_link中的每个节点有25%的概率进入最表层。以此类推。
这样就保证了表层是“高速通道”，底层是精细查找，这个思想被应用到了NSW算法中，变成了其升级版-----HNSW。
五.HNSW算法论文中的一张示意图即可看懂作者malkov的意思。
第0层中，是数据集中的所有点，你需要设置一个常数ml，通过公式floor(-ln(uniform(0,1)) x ml)来计算这个点可以深入到第几层。公式中x是乘号，floor（）的含义是向下取整，uniform（0,1）的含义是在均匀分布中随机取出一个值，ln（）表示取对数。对于上述三个函数有任何疑问的同学请下载搜狗搜索app，搜一下，什么都有。没事看看信息流，骂骂小编，苏福。
到此，关于HNSW算法的描述就基本结束了。我们来大致梳理一下它的查找过程，从表层（上图中编号为Layer=2）任意点开始查找，选择进入点最邻近的一些友点，把它们存储在定长的动态列表中，别忘了把它们也同样在废弃表中存一份，以防后面走冤枉路。一般地，在第x次查找时，先计算动态列表中所有点的友点距离待查找点（上图绿色点）的距离，在废弃列表中记录过的友点不要计算，计算完后更新废弃列表，不走冤枉路，再把这些计算完的友点存入动态列表，去重排序，保留前k个点，看看这k个点和更新前的k个点是不是一样的，如果不是一样的，继续查找，如果是一样的，返回前m个结果。
插入构图的时候，先计算这个点可以深入到第几层，在每层的NSW图中查找t个最紧邻点，分别连接它们，对每层图都进行如此操作，描述完毕。
我们需要控制一大堆参数，首先，插入时的动态列表c的大小，它的大小直接影响了插入效率，和构图的质量，size越大，图的质量越高，构图和查找效率就越低。其次，一个节点至少有几个“友点”，“友点”越多，图的质量越高，查找效率越低。作者在论文中还提到了“max友点连接数”这个参数，设置一个节点至多有多少友点，来提高查找效率，但是设的太小又会影响图的质量，权衡着来。上一段中的ml也是你来控制的，设置的大了，层数就少，内存消耗少，但严重影响效率，太大了会严重消耗内存和构图时间。在论文中，作者将查找状态下的动态列表长度和插入状态下的动态列表长度做了区分，你可以通过调整他们来实现“精构粗找”或者“精找粗构”。
文中或有疏漏，欢迎指正批评。如果各位读者对我的文章还满意的话，一听可乐的钱就可以支持我继续写作，欢迎打赏。
https://blog.csdn.net/u011233351/article/details/85116719