HNSW算法概述

HNSW（Hierarchical Navigable Small Word）算法算是目前推荐领域里面常用的ANN（Approximate Nearest Neighbor）算法了。其目的就是在极大量的候选集当中如何快速地找到一个query最近邻的k个元素。

要找到一个query的k个最近邻元素，一个朴素的思想就是我去计算这个query和所有的总量N 个候选元素的距离，然后选择其中的前k 个最小元素，这个经典算法的算法复杂度是O(Nlog(k))，显然这个算法复杂度实在是太高了，无法适用于实际的使用场景。

而要解决这个问题，可以有多种实现方法，这里所要说的HNSW算法就是目前比较常用的一种搜索算法，它算是其前作NSW算法的一个升级版本，但是两者的本质都是基于一个朴素的思路，就是通过图连接的方式给所有的N 个候选元素事先地定义好一个图连接关系，从而可以将前述的算法复杂度当中的N 的部分给减小掉，从而优化整体的检索效率。

其整体的一个图结果可以用下图进行表达：

解决的问题：做高效率相似性查找。推荐系统中，如何找到与用户query最相近的几个item，然后推荐出去【也就是推荐出与用户搜索的类似的/用户感兴趣的商品】。

解决方法有：Annoy，KD-Tree， LSH， PQ，NSW， HNSW等。

近似最近邻搜索算法（Approximate Nearest Neighbor Search，ANNS）发展：近邻图(Proximity Graph)–> NSW --> Skip List --> HNSW

近似最近邻搜索算法（Approximate Nearest Neighbor Search，ANNS）

1. 近邻图(Proximity Graph)

近邻图(Proximity Graph)： 最朴素的图算法

思路： 构建一张图， 每一个顶点连接着最近的 N 个顶点。 Target （红点）是待查询的向量。在搜索时， 选择任意一个顶点出发。 首先遍历它的友节点， 找到距离与 Target 最近的某一节点， 将其设置为起始节点， 再从它的友节点出发进行遍历， 反复迭代， 不断逼近， 最后找到与 Target 距离最近的节点时搜索结束。

存在的问题：

1. 图中的K点无法被查询到。
2. 如果要查找距离Target （红点）最近的topK个点， 而如果点之间无连线， 将影响查找效率。
3. D点有这么多友节点吗？ 增加了构造复杂度。谁是谁的友节点如何确定？
4. 如果初始点选择地不好（比如很远），将进行多步查找。

2. NSW算法原理

NSW，即没有分层的可导航小世界的结构（Navigable-Small-World-Graph ）。

针对上面的问题，解决办法：

1. 某些点无法被查询到 -> 规定构图时所有节点必须有友节点。
2. 相似点不相邻的问题 -> 规定构图时所有距离相近到一定程度的节点必须互为友节点。
3. 关于某些点有过多友节点 -> 规定限制每个节点的友节点数量。
4. 初始点选择地很远 -> 增加高速公路机制。

2.1 NSW构图算法

图中插入新节点时，通过随机存在的一个节点出发查找到距离新节点最近的m个节点（规定最多m个友节点，m由用户设置），连接新节点到这最近的m个节点。节点的友节点在新的节点插入的过程中会不断地被更新。

待更新...............

算法>推荐算法：HNSW算法简介-CSDN博客

检索模型-粗排HNSW_hnsw模型-CSDN博客