高效且稳健的近似最近邻搜索：使用层次可导航小世界图

摘要

我们提出了一种基于可导航小世界图且可控制层次结构的新近似 K‑最近邻搜索方法（层次可导航小世界图，HNSW）。该方案完全基于图结构，无需额外的搜索结构（这些结构通常用于大多数近邻图技术的粗略搜索阶段）。层次可导航小世界图逐步构建一个多层结构，由一组层次化的近邻图（层）组成，用于存储元素的嵌套子集。元素所在的最高层以指数衰减概率分布随机选择。这使得生成的图类似于先前研究的可导航小世界（NSW）结构，并且连接关系按其特征距离尺度分层。从上层开始搜索并利用尺度分离，可以提升性能，相较于 NSW 并实现对数级复杂度。采用启发式方法选择近邻图邻居，在高召回率和高度聚类数据情况下显著提升性能。性能评估表明，所提出的通用度量空间搜索索引能够显著优于以往开源的最先进仅基于向量的方法。该算法与跳表结构相似，便于实现平衡分布式部署。

作者

Yu A. Malkov Samsung AI Center，莫斯科，俄罗斯 ORCID: 0000-0003-4324-6433

D. A. Yashunin 下诺夫哥罗德，俄罗斯

发表信息

期刊: IEEE Transactions on Pattern Analysis and Machine Intelligence 年份: 2020 卷: 42 期: 4 页码: 824-836 DOI: 10.1109/TPAMI.2018.2889473 文章编号: 8594636 ISSN: Print ISSN: 0162-8828, CD: 2160-9292, Electronic ISSN: 1939-3539

指标

论文引用: 685 总下载量: 11699

资助

• 俄罗斯基础研究基金（资助号：16-31-60104 mol_a_dk）

关键词

IEEE 关键词: 路由，复杂性理论，搜索问题，数据模型，近似算法，生物系统建模，脑建模

关键词： 搜索效率, 邻域搜索, 小世界, 小图, 近似最近邻搜索, 小世界图, 可导航小世界, 启发式, 上层, 对数尺度, 数据聚类, 高召回率, 复杂缩放, 高维, 维度数据, 随机数据, 低维, 插入序列元素, 分层算法, 最近邻, 低维数据, 搜索质量, 大规模神经网络, 局部敏感哈希, 构造算法, 最近邻算法, 多对数, 搜索性能, 复杂搜索, 搜索阶段

作者关键词： 图与树搜索策略, 人工智能, 信息搜索与检索, 信息存储与检索, 信息技术与系统, 搜索过程, 图与网络, 数据结构, 最近邻搜索, 大数据, 近似搜索, 相似度搜索

第 1 节 引言

不断增长的可用信息资源导致对可扩展且高效的相似性搜索数据结构的需求激增。信息检索中普遍使用的一种方法是 K 最近邻搜索 (K-NNS)。K-NNS 假设你已经定义了数据元素之间的距离函数，并旨在从数据集中寻找 K 个元素，使其到给定查询的距离最小。此类算法被广泛应用于诸如无参机器学习算法、大规模数据库中的图像特征匹配 ¹ 以及语义文档检索 ² 等场景。K-NNS 的一种朴素做法是计算查询与数据集中的每个元素之间的距离，并选择距离最小的元素。不幸的是，朴素做法的复杂度随存储元素数量线性增长，使其在大规模数据集上不可行。这导致了对快速且可扩展的 K-NNS 算法开发的浓厚兴趣。

K-NNS 的精确解法 ³, ⁴, ⁵ 仅在相对低维数据的情况下，因“维度灾难”可能提供显著的搜索速度提升。 为克服此问题，提出了近似最近邻搜索（K-ANNS）的概念，它通过允许少量误差来放宽精确搜索的条件。 近似搜索的质量（召回率）定义为找到的真实最近邻数量与 K 的比例。 最受欢迎的 K-ANNS 方案基于树算法的近似版本 ⁶, ⁷、局部敏感哈希（LSH） ⁸, ⁹ 以及产品量化（PQ） ¹⁰, ¹¹, ¹², ¹³, ¹⁴, ¹⁵, ¹⁶, ¹⁷。 近邻图 K-ANNS 算法 ¹⁸, ¹⁹, ²⁰, ²¹, ²², ²³, ²⁴, ²⁵, ²⁶, ²⁷ 最近获得流行，能够在高维数据集上提供更好的性能。 然而，近邻图路由的幂律缩放在低维或聚类数据的情况下导致极端性能下降。

本文提出了层次可导航小世界（Hierarchical NSW, HNSW），一种全图基于增量的 K-ANNS 结构，能够提供更好的对数复杂度扩展。 主要贡献包括：明确选择图的入口节点、按不同尺度分离链接以及使用先进的启发式方法来选择邻居。 另外，Hierarchical NSW 算法可以被视为将概率跳表结构 ²⁸ 扩展为使用近邻图而非链表。 性能评估表明，所提出的通用度量空间方法能够显著优于仅适用于向量空间的前沿开源方法。

第2节 相关工作

2.1 近邻图技术

在大多数研究过的图算法中，搜索表现为在k-近邻（k-NN）图中的贪心路由形式²⁹, ³⁰, ³¹, ³², ³³, ³⁴, ³⁵, ³⁶, ³⁷, ³⁸。对于给定的邻近图，我们从某个入口点开始搜索（该入口点可以是随机的或由独立算法提供），并迭代遍历该图。在遍历的每一步，算法会检查查询点到当前基点邻居的距离，并选择使距离最小的相邻节点作为下一个基点，同时持续追踪已发现的最佳邻居。当满足某些停止条件时（例如，距离计算次数），搜索即终止。在k-NN图中，与最近邻居的连接是对德劳内图³⁹, ⁴⁰的一个简单近似（该图保证基本贪心图遍历的结果始终是最邻近点）。遗憾的是，若缺乏关于空间结构的先验信息，则无法高效构建德劳内图⁴¹；但通过仅使用存储元素之间的距离，可以利用最近邻来近似该图。研究表明，采用此类近似的邻近图方法与其他k-近似最近邻搜索（k-ANNS）技术（如kd树或LSH）相比具有竞争力⁴², ⁴³, ⁴⁴, ⁴⁵, ⁴⁶, ⁴⁷, ⁴⁸, ⁴⁹, ⁵⁰。

k-NN 图方法的主要缺点是：1) 在路由过程中，步骤数随着数据集大小呈幂律扩展 ⁵¹, ⁵²; 2) 可能出现全局连通性丧失，导致聚类数据上的搜索效果不佳。 为克服这些问题，已经提出许多混合方法，它们仅针对向量数据使用辅助算法 (如 kd-trees ⁵³, ⁵⁴ 和 product quantization ⁵⁵) 来通过粗略搜索找到更好的入口点节点候选。

在 ⁵⁶, ⁵⁷, ⁵⁸ 中，作者提出了一种基于邻近图的 K-ANNS 算法，称为可导航小世界（Navigable Small World, NSW，也称为 Metricized Small World, MSW），该算法利用可导航图，即在贪婪遍历过程中，跳跃次数随网络规模呈对数或多对数比例增长 [^31], [^32]。NSW 图通过在随机顺序下连续插入元素并双向连接到先前已插入元素中的 M 个最近邻来构建。M 个最近邻是通过从多个随机入口点节点开始的贪婪搜索变体来寻找的。插入构造开始时最近邻的链接随后成为连接网络枢纽的桥梁，保持整体图连通性并允许在贪婪路由期间跳跃次数按对数比例缩放。

NSW 结构的构造阶段可以高效地并行化，既不需要全局同步，也不会对准确性产生可测量的影响 ⁵⁹，使得 NSW 成为分布式搜索系统的良好选择。NSW 方法在某些数据集上实现了最先进的性能 [^33], [^34]，然而，由于整体多对数复杂度的扩展，该算法在低维数据集上仍易出现严重的性能下降（在这些数据集上 NSW 可能比基于树的算法低几个数量级 [^34]）。

2.2 可导航小世界模型

具有对数或多对数贪婪图路由缩放的网络被称为可导航小世界网络 [^31], [^32]。这类网络是复杂网络理论中的重要课题，旨在理解现实网络形成的潜在机制，以便将其应用于可扩展路由 [^32], [^35], [^36] 以及分布式相似度搜索 ⁶⁰, ⁶¹, ⁶², [^37], [^38], [^39], [^40]。

最早考虑可导航网络空间模型的工作由 J. Kleinberg [^31]、[^41] 完成，作为著名 Milgram 实验的社交网络模型 [^42]。Kleinberg 研究了随机 Watts-Strogatz 网络的变体 [^43]，使用在 d 维向量空间中的规则格点图，并通过遵循特定长链长度分布 r^{{-}\alpha } 对长程链接进行补充。对于 \alpha = \text{d}（在本文中，d 是 L2 空间的维度，随机数据均匀填充超立方体）来说，通过贪心路由到达目标所需的跳数呈多对数尺度（而非任何其他 \alpha 值的幂律）。这一想法激发了基于导航效应的许多 K-NNS 和 K-ANNS 算法的发展 [^37]、[^38]、[^39]、[^40]。尽管 Kleinberg 模型可以扩展到其他空间，但要构建这样的可导航网络，需要事先了解数据分布。此外，Kleinberg 图中的贪心路由的复杂度最坏情况也只能是多对数可扩展。

另一类广为人知的可导航网络是无尺度模型 [^32]、[^35]、[^36]，它们可以重现现实网络的若干特征，并被宣传用于路由应用 [^35]。然而，由此类模型生成的网络在贪心搜索方面的幂律复杂度扩展更差 [^44]，与 Kleinberg 模型一样，无尺度模型需要全局了解数据分布，使其无法用于搜索应用。

上述描述的 NSW 算法采用了一种更简单、此前未知的可导航网络模型，支持去中心化图构建，并适用于任意空间的数据。有人提出 [^44]，认为 NSW 网络形成机制可能负责大型生物神经网络的可导航性（其存在存在争议）：类似模型已能够描述小型脑网络的增长，而该模型又预测了大型神经网络中观察到的若干高级特征。然而，NSW 模型同样受到路由过程多对数搜索复杂度的限制。

第 3 节 动机

可以通过分析路由过程来识别改进 NSW 搜索复杂度的方法，该过程已在 [^32]、[^44] 中详细研究。路由可分为两个阶段：“zoom-out” 和 “zoom-in” [^32]。贪婪算法从低度节点开始，在“zoom-out”阶段遍历图的同时逐步增加节点度，直至节点链接长度的特征半径达到到查询距离的尺度。 在此之前，节点的平均度数可能相对较小，这会增加陷入遥远错误局部最小值的概率。

可以通过从最大度数节点开始搜索来避免 NSW 中描述的问题（良好候选者是首先插入 NSW 结构的节点 [^44]），直接进入搜索的“zoom-in”阶段。测试表明，将首个节点设为入口点显著提高了结构中成功路由的概率，并在低维数据上提供了显著更好的性能。然而，它的可扩展性仍然仅是单个贪婪搜索的多对数复杂度，且在高维数据上的表现不如层次 NSW。

在 NSW 中单个贪心搜索的多对数复杂度缩放的原因是，距离计算总数大致与贪心算法跳数平均值与贪心路径上节点平均度的乘积成比例。跳数平均值呈对数缩放 ⁶³, [^44]，而贪心路径上节点的平均度也因以下事实呈对数缩放：1) 随着网络增长，贪心搜索倾向于通过相同的枢纽 [^32], [^44]；2) 枢纽连接数的平均值随网络规模增加而呈对数增长。因此，我们得到最终复杂度的整体多对数依赖关系。

Hierarchical NSW 算法的思想是根据链路长度将其分隔成不同的层，然后在多层图上搜索。在这种情况下，我们可以为每个元素评估固定数量的连接，独立于网络大小，从而实现对数可扩展性。在此结构中，搜索从仅包含最长链路的上层开始（即“放大”阶段）。算法贪心地遍历上层，直到达到局部最小值（如图 1所示）。随后，搜索切换到下层（链路更短），从前一层的局部最小值元素重新开始，过程重复进行。所有层中每个元素的最大连接数可以保持常数，从而实现可导航小世界网络中路由的对数复杂度扩展。

图 1. Hierarchical NSW 思想的示意图。搜索从顶层的一个元素开始（红色显示）。红色箭头显示从入口点到查询（绿色显示）的贪心算法方向。

构建这种分层结构的一种方式是通过引入层次，显式地为不同长度尺度设置链路。对于每个元素，我们选择一个整数级别 l，该级别定义了该元素所属的最大层。对于某一层的所有元素，构建一个邻近图（即仅包含近似 Delaunay 图的“短”链路的图）并逐步增量。若我们为 l 设置指数衰减概率（即遵循几何分布），则可以得到结构中层数期望值的对数尺度。搜索过程是从顶层开始、到零层结束的迭代贪心搜索。

如果我们将所有层的元素连接合并，结构将类似于 NSW 图（此时 l 可以对应于 NSW 中的节点度）。与 NSW 不同，Hierarchical NSW 构造算法不需要在插入前对元素进行洗牌——随机性通过使用层级随机化实现，从而即使在临时改变数据分布的情况下也能实现真正的增量索引（尽管插入顺序的轻微改变会由于构造过程仅部分确定而略微影响性能）。

层级 NSW 思想也与一种众所周知的一维概率跳表结构 ⁶⁴ 十分相似，并且可以使用其术语进行描述。跳表的主要区别在于我们通过将链表替换为邻近图来泛化结构。因此，层级 NSW 方法可以利用相同的方法来构建分布式近似搜索/覆盖结构 [^45]。

在元素插入过程中，为了选择近似图连接，我们采用一种启发式方法，该方法考虑候选元素之间的距离，以创建多样化的连接（类似的算法曾在空间逼近树 ⁶⁵ 中用于选择树的子节点），而不是仅仅选择最近的邻居。该启发式方法从最接近（相对于已插入元素）开始检查候选者，并且仅当候选者比已连接的任何候选者更靠近基准（已插入）元素时才创建连接（详细信息见第4节）。

当候选者数量足够大时，该启发式方法可以获取精确的相对邻域图 [^46] 作为子图，即仅通过节点间距离可推导出的 Delaunay 图的最小子图。相对邻域图可以轻松保持全局连通分量，即使在高度聚类的数据情况下也能如此（见图 2 以作说明）。请注意，该启发式方法会比精确的相对邻域图产生额外的边，从而可以控制连接数量，这对搜索性能至关重要。对于一维数据，启发式方法仅通过元素间距离信息即可得到精确的 Delaunay 子图（此时与相对邻域图相同），从而实现层级 NSW 与一维概率跳表算法的直接转换。

Fig. 2. 描述用于选择两个孤立簇的图邻居的启发式方法。一个新元素被插入到簇 1 的边界上。该元素的所有最近邻都属于簇 1，从而导致簇间 Delaunay 图的边缺失。该启发式方法却从簇 2 中选择元素 e_{0}，从而在插入元素最接近 e_{0} 时比任何其他来自簇 1 的元素保持全局连通。

层级 NSW 接近图的一个基本变体也被用于 ⁶⁶（称为‘稀疏邻域图’）用于邻域图搜索。类似的启发式方法也是 FANNG 算法 [^47]（在本文当前版本在线发布后不久发表）的重点，基于稀疏邻域图的精确路由属性 ⁶⁷，具有略微不同的解释。

第 4 节 算法描述

网络构造（算法1）通过连续插入存储元素到图结构来组织。对于每个插入的元素，随机选择一个整数最大层 l，其概率分布呈指数衰减（由 m_{L} 参数归一化，见算法1第4行）。

插入过程的第一阶段从最顶层开始，贪婪地遍历图，以按顺序找到层中插入元素 q 的 ef 个最近邻。 随后，算法从下一层继续搜索，使用前一层找到的最近邻作为入口点，过程重复进行。 每层的最近邻是通过描述在算法 2 中的贪婪搜索算法变体找到的，该算法是来自 ⁶⁸ 的算法的更新版本。 要在某一层 l_{c^{\prime}} 中获得近似的 ef 个最近邻，搜索过程中会维护一个动态列表 W，其中包含 ef 个最近找到的元素（最初用入口点填充）。 该列表在每一步通过评估列表中尚未评估的最近元素的邻域来更新，直至列表中每个元素的邻域都已评估。 与限制距离计算次数相比，分层 NSW 停止条件具有优势——它允许丢弃那些比列表中最远元素更远的候选项，从而避免搜索结构膨胀。 与 NSW 一样，列表通过两个优先队列来模拟，以获得更好的性能。 与 NSW 的区别（以及一些队列优化）包括：1）入口点是一个固定参数；2）而不是改变多次搜索的数量，搜索质量由不同的参数 ef 控制（该参数在 NSW ⁶⁹ 中设置为 K）。 在搜索的第一阶段，ef 参数设置为 1（简单的贪婪搜索），以避免额外的参数。

INSERT(hnsw, q, M, M_{max}, efConstruction, mL)

Input: multilayer graph hnsw, new element q, number of established connections M, maximum number of connections for each element per layer Mmax, size of the dynamic candidate list efConstruction, normalization factor for level generation m_{L}

Output: update hnsw inserting element q

1 W \leftarrow \emptyset / / list for the currently found nearest elements

2 ep \leftarrow get enter-point for hnsw

3 L \leftarrow level of ep // top layer for hnsw

4 l \leftarrow \lfloor -{\ln}(unif(0..1))\cdot m_{L}\rfloor // new element's level

5 for l_{c} \leftarrow L \ldots l+ 1

6 W \leftarrow \text{SEARCH}-\text{LAYER}(q, ep, ef= 1, l_{c})

7 ep ← get the nearest element from W to q

8 for lc ← min(L, l) … 0

9 W ← SEARCH-LAYER(q, ep, efConstruction, lc)

10 neighbors ← SELECT-NEIGHBORS(q, W, M, lc) // Algorithm 3 or Algorithm 4

11 add bidirectionall connectionts from neighbors to q at layer lc

12 for each e ∈ neighbors // shrink connections if needed

13 eConn ← neighbourhood(e) at layer lc

14 if │eConn│ > Mmax // shrink connections of e

// if lc = 0 then M_{max}= M_{max0}

15 eNewConn ← SELECT-NEIGHBORS(e, eConn, Mmax, lc)

// Algorithm 3 or Algorithm 4

16 set neighbourhood(e) at layer lc to eNewConn

17 ep \leftarrow W

18 if l > L

19 set enter-point for hnsw to q

SEARCH-LAYER(q, ep, ef, lc)

Input: query element q, enter-points ep, number of nearest to q elements to return ef, layer number lc

Output: ef closest neighbors to q

1 v ← ep // set of visited elements

2 C ← ep // set of candidates

3 W ← ep // dynamic list of found nearest neighbors

4 while \vert C\vert > 0

5 c ← extract nearest element from C to q

6 f ← get furthest element from W to q

7 if distance(c, q) > distance(f, q)

8 break // all elements in W are evaluated

9 for each e ∈ neighbourhood(c) at layer lc // update C and W

10 if e\,\not\in \,v

11 v \leftarrow v\,\cup \,e

12 f ← get furthest element from W to q

13 if distance(e, q) < distance(f, q) or │W│ < ef

14 C \leftarrow C\,\cup \,e

15 W \leftarrow W\,\cup \,e

16 if \vert W\vert > ef

17 remove furthest element from W to q

18 return W

当搜索到层级小于或等于 l 时，构造算法的第二阶段被启动。第二阶段在两点上有所不同：1）ef 参数从 1 提升至 efConstruction，以控制贪婪搜索过程的召回率；2）在每个层级上找到的最近邻也被用作插入元素最佳连接的候选者（连接数由参数 M* 决定）*。

考虑了两种从候选者中选择最佳 M 邻居的方法：简单地连接到最近的元素（算法 3）和一种考虑候选元素间距离以在不同方向上建立连接的启发式方法（算法 4）。启发式方法从最靠近（相对于已插入元素）的候选者开始检查，并且仅在候选者比已连接的任何候选者更接近基（已插入）元素时才建立连接。该启发式方法还有两个额外参数：extendCandidates（默认设置为 false），该参数扩展候选集合，仅对极度聚类的数据有用；以及 keepPrunedConnections，允许为每个元素获取固定数量的连接。每层（高于零）中一个元素可拥有的最大连接数由参数 M_{max} 定义（地面层使用特殊参数 M_{max0}）。如果在建立新连接时节点已满，则其扩展的连接列表会被同样用于邻居选择的算法（算法 3 或 4）进行缩减。

SELECT-NEIGHBORS-SIMPLE(q, C, M)

Input: base element q, candidate elements C, number of neighbors to return M

Output: M nearest elements to q

return M nearest elements from C to q

SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keepPrunedConnections)

Input: base element q, candidate elements C, number of neighbors to return M, layer number lc, flag indicating whether or not to extend candidate list extendCandidates, flag indicating whether or not to add discarded elements keepPrunedConnections

Output: M elements selected by the heuristic

1 R \leftarrow \emptyset

2 W ← C // working queue for the candidates

3 if extendCandidates // extend candidates by their neighbors

4 for each e ∈ C

5 for each eadj ∈ neighbourhood(e) at layer lc

6 if eadj ∉ W

7 W \leftarrow W\,\cup \,e_{adj}

8 W_{d} \leftarrow \emptyset // queue for the discarded candidates

9 while \vert W\vert > 0 and \vert R\vert < M

10 e ← extract nearest element from W to q

11 if e is closer to q compared to any element from R

12 R ← R ⋃ e

13 else

14 W_{d} \leftarrow W_{d} \cup \,e

15 if keepPrunedConnections // add some of the discarded*//* connections from Wd

16 while │Wd│> 0 and │R│< M

17 R \leftarrow R\,\cup extract nearest element from Wd to q

18 return R

插入过程在已在零层上建立插入元素的连接时结束。

层次 NSW 中使用的 K-ANNS 搜索算法如算法 5 所示。它大致等同于具有层 l= 0 的项目的插入算法。不同之处在于，作为连接候选者在地面层找到的最近邻现在作为搜索结果返回。搜索质量由 ef 参数控制（对应于构造算法中的 efConstruction）。

K-NN-SEARCH(hnsw, q, K, ef)

Input: multilayer graph hnsw, query element q, number of nearest neighbors to return K, size of the dynamic candidate list ef

Output: K nearest elements to q

1 W ← ∅ // set for the current nearest elements

2 ep ← get enter-point for hnsw

3 L ← level of ep // top layer for hnsw

4 for lc ← L … 1

5 W ← SEARCH-LAYER(q, ep, ef = 1, lc)

6 ep ← get nearest element from W to q

7 W ← SEARCH-LAYER(q, ep, ef, lc = 0)

8 return K nearest elements from W to q

4.1 构造参数的影响

Algorithm构造参数 m_{L} 和 M_{max0} 负责维护所构造图中的小世界可导航性。 将 m_{L} 设为零（这相当于图中只有单层）并将 M_{max0} 设为 M，将产生具有幂律搜索复杂度的有向 k‑NN 图，这在先前的研究中已被充分研究 ⁷⁰, ⁷¹（假设使用算法3进行邻居选择）。 将 m_{L} 设为零并将 M_{max0} 设为无穷大，能够产生具有多对数复杂度的 NSW 图 ⁷², ⁷³。 最后，将 m_{L} 设为某个非零值，将导致可控层次图的出现，通过引入层可实现对数级搜索复杂度（见第3节）。

为了实现可控层级的最佳性能优势，不同层之间邻居的重叠（即元素邻居中也属于其他层的比例）必须很小。为了减少重叠，我们需要减少 m_{L}。然而，另一方面，降低 m_{L} 会导致在每一层上进行贪心搜索时平均跳数增加，从而负面影响性能。这导致了 m_{L} 的最优值存在。

对于最优的 m_{L}，一个简单的选择是 1/ {\ln}(M)，这对应于跳表参数 p= 1/ M，其层与层之间平均只有单个元素重叠。
在 Intel Core i7 5930K CPU 上进行的模拟表明，所提出的 m_{L} 的选择是合理的（参见图 3，展示 10m 条随机 \text{d}= 4 向量的数据）。
此外，该图表展示了在低维数据中，当将 m_{L} 从零提升时，显著的速度提升以及使用启发式方法选择图连接的效果。
由于在高维数据中，k-NN 图已经拥有非常短的贪心算法路径 ⁷⁴，很难预期同样的行为。
令人惊讶的是，将 m_{L} 从零提升会在极高维数据上产生可测量的速度提升（100k 条稠密随机 \text{d}= 1024 向量，见图 4），并且不会对分层 NSW 方法造成任何惩罚。
对于像 SIFT 向量 ⁷⁵（其具有复杂混合结构）等真实数据，提升 m_{L} 能带来更高的性能改进，但在当前设置下相比启发式方法的改进不那么显著（见图 5，展示来自 BIGANN 学习集的 5m 条 128 维 SIFT 向量的 1-NN 搜索性能 ⁷⁶）。

图 3。绘制了查询时间相对于 m_{L} 参数的曲线，针对 10M（10 million）随机向量与 \text{d}= 4。自动选择的 m_{L} 参数值 1/ {\ln}(M) 用箭头显示。

图 4。绘制了查询时间相对于 m_{L} 参数的曲线，针对 100k（100 thousand）随机向量与 \text{d}= 1024。自动选择的 m_{L} 参数值 1/ {\ln}(M) 用箭头显示。

图 5。绘制了查询时间相对于 m_{L} 参数的曲线，针对 5M SIFT 学习数据集。自动选择的 m_{L} 参数值 1/ {\ln}(M) 用箭头显示。

M_{max0}（零层中元素可拥有的最大连接数）的选择也对搜索性能有强烈影响，尤其是在高质量（高召回率）搜索的情况下。模拟显示，将 M_{max0} 设为 M（如果不使用邻居选择启发式算法，则相当于每层的 k‑NN 图）会在高召回率下导致非常严重的性能惩罚。模拟还表明，2\cdot M 是 M_{max0} 的良好选择：将该参数设得更高会导致性能下降和内存使用过度。在图 6 中展示了基于 5M SIFT 学习数据集的搜索性能结果，取决于 M_{max0} 参数（在 Intel Core i5 2400 CPU 上完成）。建议值在不同召回率下提供接近最优的性能。

图 6。绘制了查询时间相对于 M_{max0} 参数的曲线，针对 5M SIFT 学习数据集。自动选择的 M_{max0} 参数值 2\cdot M 用箭头显示。

在所有考虑的案例中，使用邻近图邻居选择启发式算法（算法 4）相比于简单地连接最近邻（算法 3）能够获得更高或相当的搜索性能。该效果在低维数据、在中维数据的高召回率以及高度聚类数据（理论上可将离散性视为局部低维特征）中最为显著，见图 7（Core i5 2400 CPU）。当使用最近邻作为邻接关系构建邻近图时，分层 NSW 算法无法在聚类数据中获得高召回率，因为搜索会在聚类边界处停滞。相反，使用启发式算法（并结合候选扩展，算法 4 的第 3 行）时，聚类效果会进一步提升搜索性能。对于均匀分布和极高维数据，邻居选择方法之间的差异很小（见图 4）。

图 7. 邻居选择方法（基线对应算法3，启发式对应算法4）对聚类（100个随机孤立簇）和非聚类 d = 10 随机向量数据的影响.

用户仅剩下的有意义的构造参数是 M。M 的合理范围是 5 到 48。仿真显示，较小的 M 通常在较低召回率和/或低维数据上产生更好的结果，而较大的 M 则在高召回率和/或高维数据上更好（如图 8 所示，使用 Core i5 2400 CPU）。该参数还决定了算法的内存消耗（与 M 成正比），因此应谨慎选择。

图 8. 对不同 M 参数在 5M SIFT 学习数据集上的层次 NSW 中，召回误差与查询时间的关系图。

efConstruction 参数的选择很直接。正如在 ⁷⁷ 中所建议的，它必须足够大，以在构造过程中产生接近 1 的 K-ANNS 召回率（0.95 已足够满足大多数用例）。与 ⁷⁸ 相同，该参数也可能通过使用样本数据进行自动配置。

构造过程可以轻松高效地并行化，仅有少量同步点（如图 9 所示），并且对索引质量没有可测量的影响。构造速度/索引质量的权衡通过 efConstruction 参数控制。图 10 展示了在 10M SIFT 数据集上搜索时间与索引构造时间之间的权衡，并表明在 4X 2.4 GHz 10 核 Xeon E5-4650 v2 CPU 服务器上，仅用 3 分钟即可为 efConstruction= 100 构造出合理质量的索引。进一步增大 efConstruction 只能略微提升性能，但会显著增加构造时间。

图 9. 对两套 CPU 系统上不同线程数的 10M SIFT 数据集层次 NSW 构造时间的展示。

图 10. 对 10M SIFT 数据集层次 NSW 的查询时间与构造时间权衡的关系图。

4.2 复杂度分析

4.2.1 搜索复杂度

单次搜索的复杂度缩放可以在假设我们构建精确的Delaunay图而非近似图的前提下严格分析。假设我们已经在某一层找到最近的元素（这由拥有Delaunay图保证），随后下降到下一层。可以证明，在该层中找到最近元素前的平均步数被一个常数所上界。

事实上，元素层级是随机抽取的，因此在遍历图时，下一节点属于上层的固定概率为 p= {\exp}(-m_{L})。然而，层内的搜索总是在到达属于更高层的元素之前终止（否则上层搜索会在不同的元素上停止），因此在第 s 步未能到达目标的概率被 {\exp}(-s\cdot m_{L}) 所上界。由此可知，层内的期望步数被几何级数求和 S= 1/ (1-{\exp}(-m_{L})) 所上界，与数据集大小无关。

如果我们假设在无限数据集大小的极限 (N\rightarrow \infty) 下，Delaunay 图中节点的平均度数被一个常数 C 所限制（这在随机欧氏数据 [^48] 的情况下成立，但在奇异空间中原则上可能被违反），那么层内距离评估的整体平均次数被一个常数 C\cdot S 所上界，与数据集大小无关。

并且由于构造方式使最大层索引的期望按 \text{O}({\log}(N)) 缩放，整体复杂度缩放为 O(log(N))，与低维数据集上的模拟结果一致。

最初假设拥有精确的 Delaunay 图在 Hierarchical NSW 中因使用近似边选择启发式而失效。因此，为了避免陷入局部最优，贪心搜索算法在零层执行回溯程序。仿真表明，至少对于低维数据（图 11，\text{d}= 4），满足固定召回率所需的 ef 参数（其决定了通过回溯中的最小跳数来确定复杂度）随 N 的增加而饱和。回溯复杂度相对于最终复杂度是一个加法项，因而根据经验数据，Delaunay 图近似的不准确性不会改变缩放。

图 11. 显示所需的 ef 参数以获得固定准确度与 \text{d}= 4 随机向量数据集大小的关系图。

对Delaunay图逼近鲁棒性的经验研究（如上所示）需要平均Delaunay图边数与数据集大小无关，以证明在Hierarchical NSW中使用固定数量连接时边的逼近程度如何。然而，Delaunay图的平均度数随维度指数级增长 [^39]，因此对于高维数据（例如 \text{d}= 128）上述条件需要极大的数据集，使得此类经验研究不可行。进一步的分析证据需要确认Delaunay图逼近的鲁棒性是否能推广到更高维空间。

4.2.2 构造复杂度

构造过程通过对所有元素的迭代插入完成，而插入一个元素仅仅是不同层次的 K-ANN 搜索序列，随后使用启发式（其在固定 efConstruction 下具有固定复杂度）。添加一个元素所需的层数期望值与数据集大小无关：

\begin{equation*} E\left[ {l + 1} \right] = E\left[ { - \ln (unif(0,1))\centerdot {m_L}} \right] + 1 = {m_L} + 1.\tag{1} \end{equation*}

因此，插入复杂度相对于 N 的缩放与搜索相同，意味着至少对于相对低维数据集，构造时间按 O(N\cdot log(N)) 缩放。

4.2.3 内存成本

Hierarchical NSW 的内存消耗主要由图连接的存储决定。每个元素在零层的连接数为 M_{max0}，其他层为 M_{max}。因此，平均每个元素的内存消耗为 (M_{max0}+ m_{L}\,\cdot M_{max})·bytes_per_link。如果我们将最大总元素数限制在大约四十亿，则可使用四字节无符号整数存储连接。测试表明，典型的接近最优 M 值通常在 6 到 48 之间。这意味着索引的典型内存需求（不包括数据本身的大小）大约为每个对象 60-450 字节，与模拟结果相符。

SECTION 5 与最先进技术的比较

Hierarchical NSW 算法在 \text{C}+ + 上实现，基于非度量空间库（nmslib）[^49]1，后者已有 NSW 实现（名称为“sw-graph”）。由于该库存在若干限制，为了获得更好的性能，Hierarchical NSW 实现使用了自定义距离函数和 C 语言风格的内存管理，这避免了不必要的隐式寻址，并在图遍历期间实现了高效的硬件和软件预取。

比较 K-ANNS 算法的性能是一项非平凡的任务，因为最先进技术不断变化，新的算法和实现层出不穷。在这项工作中，我们聚焦于与具有开源实现的欧氏空间最佳算法的比较。Hierarchical NSW 算法的实现也作为开源 nmslib 库1 并配有一个外部 \text{C}+ + 低内存、仅头文件的版本，支持增量索引构建2。

比较章节由四部分组成：与基线 NSW 的比较（第 5.1 节），与欧氏空间最先进算法的比较（第 5.2 节），在 NSW 失败的通用度量空间中重新运行 [^34] 子集测试（第 5.3 节），以及与最先进 PQ 算法在大型 200M SIFT 数据集上的比较（第 5.4 节）。

5.1 与基线 NSW 的比较

对于基线 NSW 算法实现，我们使用了 nmslib 1.1 中的“sw-graph”（与在 [^33]、[^34] 中测试的实现稍有更新），以展示速度和算法复杂度（以距离计算次数衡量）的提升。

图 12(a) 展示了 Hierarchical NSW 与 NSW 在 \text{d}= 4 随机超立方数据上的比较，该数据在 Core i5 2400 CPU（10-NN 搜索）上生成。Hierarchical NSW 在对数据集进行搜索时使用的距离计算次数明显更少，尤其在高召回率时更为显著。

图 12. NSW 与 Hierarchical NSW 的比较： (a) 距离计算次数与准确率折衷，针对 1000 万个 4 维随机向量数据集； (b‑c) 性能按距离计算次数（b）和原始查询时间（c）在 8 维随机向量数据集上的缩放。

在一个 \text{d}= 8 随机超立方体数据集上，针对固定召回率 0.95 的 10-NN 搜索，算法的规模化表现如图 12(b) 所示。结果清楚表明，Hierarchical NSW 在此设置下的复杂度扩展不逊于对数级，并且在任何数据集大小下都优于普通 NSW。由于改进的算法实现，其绝对时间上的性能优势（图 12(c)）甚至更高。

5.2 欧氏空间中的比较

主要的比较是在向量数据集上完成的，使用流行的 K-ANNS 基准测试 ann-benchmark3 作为测试平台。测试系统利用算法的 Python 绑定——因此，它随后对一千个查询（通过对初始数据集随机划分提取）执行 K-ANN 搜索，使用预设的算法参数，输出包含召回率和单次搜索的平均时间。考虑的算法包括：

1. 来自 nmslib 1.1 的基线 NSW 算法（“sw-graph”）。

2. FLANN 1.8.4 ⁷⁹。一个流行的库4，包含若干算法，并内置于 OpenCV5。我们使用可用的自动调优程序，进行了多次重跑以推断最佳参数。

3. Annoy6，2016年2月2日构建版本。一个流行的基于随机投影树森林的算法。

4. VP-tree。一个通用度量空间算法，采用度量剪枝 [^50]，作为 nmslib 1.1 的一部分实现。

5. FALCONN7，版本 1.2。一个针对余弦相似度数据的新型高效 LSH 算法 [^51]。

比较是在一台 4 核 Xeon E5-4650 v2 Debian OS 系统上进行的，配备 128 GB 内存。对于每个算法，我们在每个召回率范围内精心挑选最佳结果，以评估最佳可能性能（使用测试平台默认值的初始参数）。所有测试均采用单线程模式进行。Hierarchical NSW 使用 GCC 5.3 并开启 -Ofast 优化标志进行编译。

所用数据集的参数和描述列于表 1。除了 GloVe 数据集外，我们对所有数据集使用 L2 距离；对 GloVe 数据集则使用余弦相似度（在向量归一化后相当于 L2）。暴力搜索（BF）时间由 nmslib 库测量。

表 1

向量数据的结果如图 13 所示。对于 SIFT、GloVE、DEEP 和 CoPhIR 数据集，Hierarchical NSW 明显优于竞争对手，优势显著。对于低维数据 (\text{d}= 4)，Hierarchical NSW 在高召回率下略快于 Annoy，但远超其他算法。

图13. 对比层级NSW与五个数据集上10-NN搜索的开源K-ANNS算法实现的结果。暴力搜索时间标记为BF。

5.3 在一般空间中的比较

最近对 [^34] 在一般空间（即非对称或违反三角不等式）中的算法比较显示，基线 NSW 算法在低维数据集上存在严重问题。为测试层级 NSW 算法的性能，我们重复了 [^34] 中 NSW 表现不佳或次优的测试子集。为此，我们使用了 nmslib 内置的测试系统，该系统包含用于运行 [^34] 中测试的脚本。被评估的算法包括 VP-tree、置换技术（NAPP 和暴力过滤）[^49]、[^52]、[^53]、[^54]、基本 NSW 算法和 NNDescent 生成的邻近图 ⁸⁰（与 NSW 图搜索算法配对）。与原始测试相同，对于每个数据集，测试包括 NSW 或 NNDescent 的结果，取决于哪种结构表现更好。在此情况下，层级 NSW 未使用自定义距离函数或特殊内存管理，导致一定的性能损失。

这些数据集在表2中进行了总结。有关数据集、空间和算法参数选择的进一步细节可见原始工作 [^34]。暴力搜索（BF）时间使用 nmslib 库测量。

表2

结果如图14所示。层级 NSW 显著提升了 NSW 的性能，并在所有测试数据集上成为领导者。对 NSW 最强的提升，几乎是三倍数量级，出现在维度最低的 wiki-8 数据集（使用 JS-散度）。这是一项重要结果，证明了层级 NSW 的鲁棒性，因为原始 NSW 在该数据集上是个瓶颈。请注意，为消除 wiki-8 的实现影响，结果以距离计算次数而非 CPU 时间呈现。

图14. 对比层级 NSW 与非度量空间库中一般空间 K-ANNS 算法在五个数据集上10-NN搜索的结果。暴力搜索时间标记为 BF.

5.4 基于产品量化的算法比较

产品量化 K-ANNS 算法 ⁸¹, ⁸², ⁸³, ⁸⁴, ⁸⁵, ⁸⁶, ⁸⁷, ⁸⁸ 被视为千亿级数据集的最先进技术，因为它们能够有效压缩存储的数据，允许适度的 RAM 使用，同时在现代 CPU 上实现毫秒级搜索时间。

为了比较层级 NSW 与 PQ 算法的性能，我们使用 Facebook 的 Faiss 库8作为基准（该库包含最新的 PQ 算法 ⁸⁹、⁹⁰ 的实现，且在当前手稿提交后才发布），并以 OpenBLAS 后端编译。测试在 1B SIFT 数据集的 200M 子集 ⁹¹ 上进行，使用配备 128GB 内存的 4X Xeon E5-4650 v2 服务器。由于 ann-benchmark 测试平台依赖 32 位浮点格式（仅存储数据就需要超过 100GB），因此不适合本实验。为了获取 Faiss PQ 算法的结果，我们使用了 Faiss wiki9 中参数的内置脚本。对于层级 NSW 算法，我们使用了一个在 nmslib 之外的特殊构建，具有较小的内存占用、简单的非向量化整数距离函数，并支持增量索引构建10。

结果如图 15 所示，并在表 3 中总结了参数。峰值内存消耗是通过在两种算法的索引构建后，使用 Linux “time –v” 工具在单独的测试运行中测量的。尽管层级 NSW 需要显著更多的 RAM，但它可以实现更高的准确率，同时在搜索速度上提供巨大的提升，并且索引构建速度更快。

图 15 在 200M SIFT 数据集 [13] 上与 Faiss 库的比较结果。图中嵌入图显示了层级 NSW 的查询时间相对于数据集大小的缩放。

表 3

图 15 的嵌入图展示了层级 NSW 的查询时间与数据集大小的缩放关系。请注意，该缩放偏离了纯对数关系，可能是由于数据集相对较高的维度导致的。

第 6 节 讨论

通过对可导航的小世界图进行结构分解，并结合智能邻居选择启发式，所提出的层级 NSW 方法克服了基本 NSW 结构的若干重要问题，推动了 K-ANN 搜索技术的前沿。层级 NSW 在大量数据集上表现卓越，成为明显的领跑者，尤其在高维数据情况下，以显著优势超过开源竞争对手。即使在以前的算法（NSW）相差数个数量级的数据集上，层级 NSW 仍能取得第一名。层级 NSW 支持连续增量索引，也可用作高效获取 k-NN 及相对邻域图近似值的方法，而这些近似值是索引构造的副产品。

该方法的鲁棒性是一大优势，使其在实际应用中非常有吸引力。该算法适用于广义度量空间，在本文测试的任何数据集上均表现最佳，从而消除了为特定问题选择最佳算法的复杂需求。我们强调该算法鲁棒性的重要性，因为数据可能在不同尺度下具有不同的有效维数，结构复杂。举例来说，一个数据集可以由点组成，位于随机填充高维立方体的曲线上，因而在大尺度下是高维，在小尺度下则为低维。为了在此类数据集中进行高效搜索，近似最近邻算法必须在高维和低维两种情况均表现良好。

还有多种方法可以进一步提升层级 NSW 方法的效率和适用性。仍有一个重要参数未定，它对索引构造影响很大——每层新增连接数 M。有可能直接通过使用不同的启发式方法来推断该参数 ⁹²。还可以比较层级 NSW 在完整 1B SIFT 和 1B DEEP 数据集上的表现 ⁹³, ⁹⁴, ⁹⁵, ⁹⁶, ⁹⁷，并添加对元素更新和删除的支持。

相较于基础 NSW，所提出的方法的明显缺点之一是失去了分布式搜索的可能性。层次化 NSW 结构中的搜索始终从顶层开始，因此无法像在 ⁹⁸ 所述的那样使用相同的技术将其分布化，因为上层元素的拥塞。可以使用简单的变通办法来分布化该结构，例如将数据划分到 ⁹⁹ 研究的集群节点上，然而在这种情况下，系统的总并行吞吐量并不能随计算机节点数良好扩展。

不过，还有其他已知的方法可以将这种结构分布化。层次化 NSW 在思想上与众所周知的一维精确搜索概率跳表结构非常相似，因此可以使用相同的技术将其分布化 [^45]。这可能导致比基础 NSW 更好的分布式性能，因其具有对数级扩展性，并且理想情况下节点负载均匀。

注脚

. https://github.com/nmslib/nmslib .

. https://github.com/nmslib/hnsw .

. https://github.com/erikbern/ann-benchmarks .

. https://github.com/mariusmuja/flann .

. https://github.com/opencv/opencv .

. https://github.com/spotify/annoy .

. https://github.com/FALCONN-LIB/FALCONN .

. https://github.com/facebookresearch/faiss 2017 年 5 月构建。从 2018 年开始，Faiss 库已经拥有自己的层次化 NSW 实现。

. https://github.com/facebookresearch/faiss/wiki/Indexing-1G-vectors .

. https://github.com/nmslib/hnsw .

参考文献

额外参考文献