Hierarchical Navigable Small Worlds (HNSW)

https://www.pinecone.io/learn/series/faiss/hnsw/

这篇博客深入浅出地介绍了用于向量相似性搜索的顶级索引技术——分层可导航小世界（HNSW）图。文章从理论基础、图构建、Faiss库的实现到参数调优，全面解析了HNSW的工作原理和性能特点。

🧬 HNSW 的理论基础

HNSW 属于近似最近邻（ANN）搜索算法中的“图”类别。它的诞生融合了两种关键技术：

1. 概率跳表 (Probability Skip List)：HNSW 借鉴了其分层结构。在跳表中，顶层的链接可以“跳过”大量中间节点，实现快速查找；越往下层，链接越短，用于精确定位。
2. 可导航小世界图 (Navigable Small World, NSW)：这是一种通过长短程链接结合的图结构，能以对数级复杂度实现高效的贪婪路由搜索。搜索时，算法从一个入口点开始，每次都贪婪地移动到离目标更近的邻居节点，直到找到局部最优解。

HNSW 将两者结合，构建了一个分层的 NSW 图。顶层拥有最长的链接，用于快速“放大”定位区域；底层链接密集且短，用于“缩小”范围并精确查找。

🏗️ 图的构建过程

HNSW 图的构建是逐个插入向量完成的，其核心步骤如下：

1. 分层插入：每个新向量会根据一个概率函数被分配一个插入层级。绝大多数向量只存在于最底层（Layer 0），只有少数“幸运儿”能出现在更高层。
2. 贪婪寻路：从顶层入口开始，算法通过贪婪搜索，在每一层找到离新向量最近的节点，然后下降到下一层继续搜索，直到达到该向量的插入层。
3. 建立连接：在插入层，算法会扩大搜索范围（由 efConstruction 参数控制），找到一批最近的邻居作为候选。然后从中选出 M 个最近的邻居，与新向量建立连接。
4. 逐层连接：这个过程会在新向量所在的层级及其以下所有层级重复，确保它在每一层都与最近的邻居相连。

⚙️ Faiss 中的实现与参数

文章以 Faiss 库为例，展示了 HNSW 的实现和关键参数：

• M：每个向量在每一层最多拥有的邻居数量。它直接影响图的密度、内存占用和搜索质量。
• efConstruction：建图时的搜索范围。值越大，为新向量挑选的邻居质量越高，图的结构越好，但建图速度更慢。
• efSearch：搜索时的考察范围。值越大，搜索时考察的候选点越多，结果的召回率（Recall）越高，但搜索速度会变慢。

📈 性能权衡

文章通过实验分析了参数对性能的影响，揭示了 HNSW 的核心权衡：

• 召回率 (Recall)：更高的 M、efConstruction 和 efSearch 值都能显著提升搜索的召回率。
• 搜索速度 (Search Time)：追求高召回率的代价是搜索时间会显著增加。efSearch 对搜索时间的影响最为直接。
• 内存占用 (Memory Usage)：内存占用主要由 M 决定。M 值越大，图的连接越多，索引占用的内存也越大。efConstruction 和 efSearch 对内存没有影响。

总而言之，HNSW 通过其巧妙的分层图结构实现了极快的搜索速度和极高的召回率，但需要在使用时根据具体场景，在搜索精度、速度和内存成本之间进行权衡和调整。

https://towardsdatascience.com/similarity-search-part-4-hierarchical-navigable-small-world-hnsw-2aad4fe87d37/

这篇博客详细介绍了分层可导航小世界（HNSW）算法，这是一种用于近似最近邻搜索的先进方法。

🎯 核心思想

HNSW 的核心目标是构建一个多层图结构，使得图中任意两个节点之间都能通过很少的步骤（跳跃）到达，从而实现高效的搜索。

🧩 基础概念

在深入 HNSW 之前，文章先介绍了两个关键的数据结构：

1. 跳表 (Skip List)：一种概率性数据结构，通过多层链表实现快速查找。搜索从顶层开始，逐层向下，跳过大量元素，平均时间复杂度为 O(log n)。HNSW 借鉴了其分层跳跃的思想。
2. 可导航小世界 (NSW)：一种图结构，使用贪婪路由进行搜索。搜索从一个入口点开始，每次都移动到离查询点更近的邻居节点，直到无法找到更近的节点为止。这种方法可能会遇到“过早停止”的问题，即陷入局部最优解。

🔍 HNSW 算法详解

HNSW 结合了跳表和 NSW 的优点，构建了一个分层的图。

搜索过程

1. 从图的最顶层开始，选择一个入口点。
2. 在当前层使用贪婪算法找到离查询点最近的邻居。
3. 将这个最近的邻居作为下一层的入口点，重复上述过程，直到抵达最底层（第 0 层）。
4. 在最底层找到的最近邻居即为最终结果。

构建过程

1. 确定层级：为每个新插入的节点随机分配一个最大层级 l。这个层级遵循指数衰减的概率分布，这意味着大多数节点只存在于最底层，只有少数节点会出现在更高的层级。
2. 逐层插入：
   • 从最高层开始，贪婪地找到离新节点最近的节点，并将其作为下一层的入口点。
   • 当到达该节点的最大层级 l 时，开始在该层及所有更低层级进行连接。
   • 在每一层，算法会先找到 efConstruction 个候选近邻，然后通过一个启发式算法从中选出 M 个节点进行连接。

关键参数与启发式算法

• M: 每个节点在每一层最多连接的邻居数量。
• efConstruction: 构建索引时探索的候选邻居数量。值越大，构建的图质量越高，但耗时也越长。
• mL: 控制节点层级分布的参数。
• 候选选择启发式算法: 为了避免将新节点连接到彼此非常接近的邻居（这不利于图的连通性），该算法不仅考虑距离，还考虑图的连通性。它会优先选择那些能连接到不同区域的邻居，从而优化整个图的导航效率。

🛠️ 实践应用与 Faiss 实现

文章还介绍了如何使用流行的相似性搜索库 Faiss 来实现 HNSW。

• IndexHNSWFlat: Faiss 中实现 HNSW 的基础类，用于存储原始向量。
• 组合索引: HNSW 可以与其他方法结合使用以提升性能。一个常见的例子是将其与倒排文件（IVF）和乘积量化（PQ）结合（IndexIVFPQ）。在这种组合中，HNSW 充当“粗量化器”，负责快速定位最近的 Voronoi 分区（聚类中心），从而大大缩小后续精确搜索的范围。

总而言之，HNSW 通过其巧妙的多层图结构和启发式连接策略，在处理大规模向量数据时，能够在保持较高搜索精度的同时，实现极快的搜索速度。