向量检索通过将文本、图像、音频等非结构化数据转换为数值向量，然后在向量空间中计算这些向量之间的相似度或距离，通过近似最近邻搜索（Approximate Nearest Neighbor Search, ANNS）算法对特征向量的计算能够实现对非结构化数据的快速检索，以实现相似项的检索。向量检索在多模态的非结构化数据日益增多的今天显得尤为重要。向量检索在CV、NLP、RAG、搜索引擎、推荐系统和在线广告中应用十分广泛。比如，利用距离计算和向量检索技术，可以为目标用户推荐与其最匹配的Top-K物品，比如基于目标用户最近点击或购买过的物品，推荐与之最相似的Top-K物品。
向量检索常用的ANNS算法。不同于 KNNS（K-Nearest Neighbors Search）的精确搜索，ANNS不要求最终的结果一定是前K个最近向量，允许一定的误差。在大部分场景中，本身就不需要一定精确的搜索，牺牲少量的精确性能够换来很大的性能提升，比如在推荐系统当中，需要根据用户画像从候选池中召回物品，但是如果每次召回的都是相似的物品，也会使得用户陷入信息茧房降低使用体验。
HNSW是一种基于图的向量检索算法。当我们简单地讨论二维向量时，每个二维向量都是二维平面上的一个点。当各个向量之间没有任何关联时，需要找到当前向量的前K个相近向量，需要遍历空间中的所有二维向量，时间复杂度为O(n)，这个性能是完全无法接受的。而所谓的图检索，就是给向量节点之间构建一个关系，这种节点之间的关系能够使得搜索时能按照大致的路线进行，而无需再遍历所有的节点，大大提高检索的效率。
NSW算法
HNSW（Hierarchical Navigable Small World Graphs）算法在NSW（Navigable small world）算法的基础上，加入了层级结构，从而使检索速度更快。二者是同一作者，因此先从NSW算法切入。
NSW的基本思想是在构建图的过程中，为每个向量（节点）找到并建立与其最近的若干点（邻居）的连接。这样，当图构建完成时，每个点都能快速访问到自己最近的几个邻近的向量，如图1所示。在NSW中，每个节点都与其邻居节点相连，这些连接基于节点之间的相似度或距离，这种存储结构允许算法在搜索时能够快速地从一个节点跳转到另一个节点，直到找到目标节点或其近似邻居。
图 1 二维向量图结构
实线为已经入库的节点，虚线为Query。然后从Entry Point节点（固定，每次检索都从此节点开始）进入，找到Entry Point离Query最近的节点A，然后继续从A的邻居节点寻找离Query最近的节点B。继续从B的邻居节点开始，找到其中离Query最近的C节点，搜索结束。当然，在大部分情况下，最终找到的节点并不一定是全局离Query最近的节点，可能有其他更加临近的节点但是并不在这条搜索路径上，这就是牺牲了一部分准确性换取的检索效率的提高。
但是考虑某种极端情况，就是当Entry Point节点本身离Query的距离相当远，横跨了整个图，那么就需要多次步进才能够完成检索。
思考一下我们在乘坐交通工具进行长途出行的时候是怎么做的？先乘坐飞机或者高铁，再换地铁，再打车最后步行到目的地，NSW解决该问题的办法类似，就是是在一些较远的点之间建立连接，让起初的搜索步长更大。那么NSW是如何在点之间建立这样的“高速通道”的呢？其实并不需要任何操作，NSW天然支持“高速通道”。因为在NSW的增量索引构图当中，起初节点是比较稀疏的，因此节点之间建立的路径相对于后期较为稠密的索引也就长了许多，构图初期建立的索引大部分为高速通道，而后期基本都是近邻索引。想象一下，当A节点是最后加入图的，在A加入之前已经有了一条Entry Point到达B的路径，所以在上述搜索过程中Entry Point能够直接步进到B节点而不需要经过A节点，如图2。
然而，这种高效的搜索能力是以空间开销为代价的。由于每个节点都需要存储到其邻居的引用，由此带来的开销就是在高维空间中空间放大，导致高维向量的索引结构会非常大。
图 2 NSW的“高速通道”
索引构建
NSW算法在增量构建索引时，为每个新插入的节点找到最近的M个节点，然后与这M个点连通。假设M=3，图2展示了一个简单的二维向量NSW索引构图过程。红色的点代表每次新加入的向量节点，红边代表它与3个近邻相连。
图 3 NSW增量索引图构建过程
查找过程
算法需要找到目标的Top K邻近节点，因此需要维护一个大小为K的优先队列。假设需要红色节点T的3个邻近点。维护三个点集，Result点集即一个大小为3的优先队列；Candidate点集即当前正在探索的点的集合，按照距离目标节点从近到远排序；Visited点集即已经被访问过的节点。
过程如图4所示，从绿色节点A出发，然后探索A的三个邻近点C、E、B。因为E距离目标T最近，因此从E的邻近点D和F开始继续探索，同时根据距离维护大小为3的优先队列Result点集。继续从最近的F点探索邻近点G，此时发现Candidate点集中所有点离T的距离均比Result点集中最远的点还要远，搜索结束，返回点集Result为最终结果。
图 4 NSW查找过程
HNSW算法
随着数据量和向量维度的增大，NSW每个向量节点的度会非常大，这就导致需要大量的内存来存储这些节点之间的连接。同时NSW算法本身并不包含剪枝机制，这意味着算法在检索过程中不会主动减少搜索空间，而是依赖于节点的邻居关系来进行搜索，导致耗时很高。为了解决这些问题，NSW的作者在其的基础上进行了改进，提出了HNSW（Hierarchical Navigable Small World）算法。HNSW通过引入层次化的图结构并保留了“高速通道”机制，允许搜索在不同层级间快速跳转，从而减少了查询路径经过的点。通过层次化的结构来控制每个点的度，避免了在高维空间中邻居数量过多的情况。这种方法在保持NSW结构特点的同时，通过引入不同特征距离尺度的链接，实现了层次化，从而提高了搜索效率并控制了空间开销。
HNSW就是NSW与跳表的结合。在一个有序的连续空间的数组中查找一个数比较高效的方式是通过二分查找，但是在链表当中，由于节点的空间并不连续，因此即使链表是有序的，我们也无法利用链表有序的特性来提高查找效率，只能从头开到尾的遍历，查询效率低，时间复杂度是O(n)。跳表简单来讲就是通过分层的结构，利用链表有序这个特性来提高查找效率，非常典型的空间换时间的算法，跳表的结构如图5所示。通过在多个层级上维护有序链表来实现快速搜索、插入和删除操作。最下层是完整的链表，在每个节点中，以一定的概率向上层“跳跃”，从而在多层链表中形成一种“梯子”结构。
图 5 跳表的结构
HNSW算法构建了一个多层次的结构，每一层都是一个NSW图，越往上层越稀疏，越往下层越稠密。最下层（Layer 0）是一个完整的NSW，相对稠密，但是即使是最下层的图，也会比普通的NSW构建的图稀疏，因为HNSW在构图时进行了更多的剪枝，其结构如图6所示。
图 6 HNSW结构
HNSW算法将链接根据它们的长度尺度分离到不同的层中，这样在搜索时可以在多层图中进行，从而允许在每个元素上独立地评估所需的固定部分连接，实现了对数复杂度的扩展。以最上层作为Entry Point开始检索，找到最接近目标的节点，然后通过该节点跳到下一层，以此类推。简而言之，就是通过上层的索引定位到下层的Entry Point，这样就会极大减少下层的查找次数。
同样的，由于HNSW其实也是用空间换时间的算法，分层结构的维护以及不同层之间索引节点的冗余存储势必会增加内存占用。
