# 1603.09320_HNSW: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

* 首页: <https://arxiv.org/abs/1603.09320>
* PDF: <https://arxiv.org/pdf/1603.09320.pdf>
* IEEE: <https://ieeexplore.ieee.org/abstract/document/8594636>
* 引用: 2322(2025-09-17)
* 组织:
    * Russian Academy of Sciences（俄罗斯科学院）

## 总结

**简介**
* 这篇论文是近似最近邻（ANN）搜索领域的一篇里程碑式的著作，它提出的 **HNSW（Hierarchical Navigable Small World）** 算法极大地影响了工业界和学术界，至今仍是性能最好的ANN算法之一。
* 核心内容是：提出了一种名为HNSW的图结构，用于高效、鲁棒地进行近似最近邻搜索
* 这篇论文是ANNS领域必读的经典论文，其提出的HNSW算法至今仍是许多实际应用的首选方案。
* 缩略
    * ANNS: Approximate Nearest Neighbors Search
    * HNSW: Hierarchical Navigable Small World
    * LSH: locality-sensitive hashing





## From Deepseek

### 1. 核心问题：近似最近邻搜索（ANNS）
在高维空间中，精确最近邻搜索（“找到绝对最近的点”）的计算成本非常高，被称为“维度灾难”。因此，实际应用中通常使用 **近似** 最近邻搜索（ANNS），其目标是“以极高的概率找到足够近的点”，同时牺牲一点点精度来换取巨大的速度提升。

### 2. 现有技术的局限性
在HNSW之前，主流ANNS方法包括：
*   **树形结构**（如KD-Tree）：在高维空间效率急剧下降。
*   **哈希方法**（如Locality-Sensitive Hashing, LSH）：需要大量内存来保证精度，性能对参数敏感。
*   **平面图**（如NSW, Navigable Small World graphs）：性能很好，但仍有优化空间，特别是在处理不同分布的数据时。

论文指出，这些方法在**查询效率、内存使用、鲁棒性**（对不同数据分布的适应性）和**易用性**（需要调优的参数多少）之间难以取得最佳平衡。

### 3. HNSW的核心思想：继承与创新
HNSW并非完全从零开始，它是对 **NSW（Navigable Small World）** 图的重大改进。其核心创新在于引入了**层次化**结构。

*   **NSW（可导航小世界图）是什么？**
    NSW受启发于人类社会的“六度分隔理论”。它构建的图同时具有**短链**（连接邻近节点的边，保证局部精度）和**长链**（连接遥远节点的边，保证全局搜索能力，避免陷入局部最优）。搜索时，从一个或多个入口点开始，像“贪婪的登山者”一样，沿着图不断走向更接近查询点的邻居，直到无法更接近为止。

*   **NSW的缺点：**
    为了应对各种查询，NSW需要足够多的“长链”，但这使得图的平均度数变高，增加了计算复杂度。对于所有数据点都放在同一层的图，搜索路径可能很长，效率不够极致。

*   **HNSW的解决方案：分层**
    HNSW的核心是将一张图变成了**多层**结构（类似于跳表SkipList的思想）。
    *   **第0层**：包含所有数据点。
    *   **更高层（第1, 2, ...层）**：是下面一层的随机子集，数据点越来越少。层数越高，图中的“长链”作用就越明显。
    *   **构建规则**：一个新元素以指数衰减的概率`exp(-ln(M))`被插入到上层中（`M`是一个参数）。这意味着大多数点只在底层，越往上点越少。


    *（这是一个简化的HNSW结构示意图，展示了从顶层到底层的搜索路径）*

### 4. HNSW的工作原理

#### A. 搜索（查询）过程
查询过程是HNSW高效性的最佳体现。
1.  **从上至下搜索**：从最高层的某个入口点开始。
2.  **逐层细化**：在**当前层**执行类似NSW的贪婪搜索，找到一个局部最近点。
3.  **向下移动**：将这个局部最近点作为下一层的入口点，重复步骤2。
4.  **底层精确搜索**：到达第0层（最底层）后，进行最终的贪婪搜索，得到最终的近似最近邻结果。

**这种策略的妙处在于**：高层结构用很少的点快速定位到查询目标所在的大致区域，避免了在底层进行漫长的全局遍历。底层则负责在这个小区域内进行精细搜索。这大大减少了需要访问的节点数量，显著提升了搜索速度。

#### B. 插入（构建）过程
构建图的过程与搜索过程类似，也是分层进行的。
1.  为新元素`q`随机一个最高层`l`（根据指数衰减概率）。
2.  从顶层开始，找到该层中离`q`最近的入口点。
3.  沿着层次结构向下，在每一层执行搜索，找到`q`的`efConstruction`个最近邻（`efConstruction`是一个构建参数）。
4.  到达指定的层`l`后，将`q`插入到图中，并在**每一层**（从层`l`到第0层）为它建立连接。连接的原则是使用**启发式连接**算法（论文中称为**邻居选择启发式**），从搜索到的候选集中选择最优的`M`个邻居进行连接，而不是简单连接最近的几个。这保证了图的良好导航特性（即同时具有短链和长链）。

### 5. HNSW的主要优势和贡献

1.  **极高的效率**：达到了当时（2016年）的**State-of-the-Art**（SOTA）性能。查询复杂度可达**对数级别**（O(log N)），比许多竞争对手快数个数量级。
2.  **出色的鲁棒性**：对多种数据分布（均匀、聚类、高维等）都能表现良好，不需要针对特定数据集进行大量的参数调优。
3.  **强大的通用性**：不仅适用于欧氏距离（L2），也适用于余弦相似度、汉明距离等多种度量方式。
4.  **简单易用**：虽然算法背后理论复杂，但实际需要调节的参数较少（主要是`M`和`efConstruction`），易于上手。
5.  **丰富的理论分析**：论文不仅提出了算法，还提供了详细的理论基础，将其与SkipList和NSW联系起来，并分析了其复杂度和搜索效率。

### 6. 总结与应用

总而言之，这篇论文的**主要内容**是：
*   指出了高维近似最近邻搜索的挑战和现有方法的不足。
*   提出了**分层图结构HNSW**，将跳表的多层思想与NSW的小世界图思想巧妙结合。
*   设计了高效的**分层搜索**和**启发式插入**算法。
*   通过大量实验证明，HNSW在速度和精度上全面超越了当时的其他主流方法。

**应用**：HNSW因其卓越的性能，被广泛应用于：
*   推荐系统（寻找相似商品或用户）
*   图像检索（寻找相似图片）
*   自然语言处理（文本语义匹配）
*   机器学习数据库（如Facebook的FAISS、微软的SPTAG等开源库都集成了HNSW）
*   任何需要“以空间换时间”进行快速相似性搜索的场景。