搜索像光速—(1)基于图的索引结构HNSW

英文原文地址：https://medium.com/dataman-in-ai/search-like-light-speed-1-hnsw-c5b0d4665926

光速搜索 — 基于图的索引结构HNSW

2023 年 10 月 20 日

我喜欢《玩具总动员》里的太空护林员“巴斯光年”，我喜欢他的口头禅“飞向无限！” 当我搜索信息时，我也享受找到正确信息的速度。这一切都是因为高速互联网和足够的带宽吗？不完全是！事实上，近乎即时搜索结果的算法是至关重要的。信息检索速度是计算机科学中的一个重要课题。随着文本、图像或音频数据的大型语言模型（大语言模型）的高维Embeddings，信息检索的速度是数据科学中的一个优先课题。

在这篇文章中，我将讨论:

• NLP中的向量Embeddings
• KNN (K-Nearest Neighbors)无法跟上速度
• 近似最近邻(ANN)感觉就像光速
• 快速搜索的初始算法
• 理解分层导航小世界图算法(HNSW)
• 代码示例：Embedding新闻文章
• 代码示例：FAISS用于HNSW搜索

本文及其后续系列解释了使巴斯光年的梦想成为可能的最先进算法。您将对这一领域及其应用的重要性有一个景观理解。您将有动手编码示例。我们开始吧。

NLP中的向量Embeddings

向量Embeddings是自然语言处理（NLP）中的一个基本概念，是单词、句子、文档、图像、音频或视频数据等对象的数字表示。这些Embeddings的目的是捕获它们所表示的对象的语义和上下文信息。

让我们首先描述一下单词Embeddings。2014年，一个突破性的想法Word2Vec(发音为“Word - to - Vector”)在自然语言处理中被提出，它将单词或短语转换或“嵌入”为数字的高维向量，称为单词Embeddings。这些词Embeddings捕捉词之间的语义和上下文关系，使机器能够理解和使用人类语言。图1显示了三维空间中的高维向量。“铁（iron）”这个词与“火药（gunpowder）”、“金属（metals）”和“钢（steel）”等词很接近，但与“有机（organic）”、“糖（sugar）”或“谷物（grain）”等不相关的词相去甚远。例如，猫和狗的概念可能很接近。

文字Embeddings

单词Embeddings可以实现单词的相似或不相似。这是一项了不起的创新。既然单词可以嵌入，为什么句子不能呢？这就是句子Embeddings的诞生。句子Embeddings捕获整个句子的语义和上下文信息，使机器能够理解和比较句子。生成句子Embeddings的常用方法包括Doc2Vec (Document-to-vector)。强大的基于llm的词Embeddings将成为NLP的标准，如BERT(来自Transformers的双向编码器表示)、ELMo(来自语言模型的Embeddings)、Llama(大型语言模型元AI，由Meta AI于2023年2月推出)，以及OpenAI的多个模型。

既然文本可以作为向量嵌入，为什么不能嵌入图像呢？这就产生了图像Embeddings。卷积神经网络(cnn)和视觉几何组(VGG)用于生成图像Embeddings。图像Embeddings使图像检索和分类成为可能。

既然图像可以作为矢量嵌入，为什么不能嵌入音频呢？你说得对！音频Embeddings可以捕获音频数据的声学特征，并可以进行音频分类和检索。视频Embeddings如何？它们捕获图像特征流用于视频分类。那么地理空间Embeddings呢？当然可以。纬度和经度坐标等地理空间数据可以嵌入到高维向量中，便于信息检索。

Embeddings使一切变得简单。如果你有一篇文章，需要找到类似的文章，你只需要计算你的文章的向量到其他文章的向量之间的距离。最近的向量就是你的搜索结果。我们可以用k近邻法（KNN），对吧？然而，速度是个问题。KNN的搜索将使光年皱眉。对于巴斯光年来说，完成一次简单的搜索需要…需要不知道多少年。研究的挑战不是最近的邻居在哪里，而是“如何”找到它们。

k-最近邻(KNNs)无法跟上速度

假设你有一本新书，你想在图书馆找到类似的书。k-最近邻（KNN）将浏览书架上的每一本书，并将它们从最相似到最不相似的顺序排列，以确定最相似的书。你有耐心做这么麻烦的工作吗？相反，人工神经网络对图书馆中的图书进行预排序和索引。要找到与你的新书相似的书，你所需要做的就是去正确的楼层，正确的区域，正确的通道找到相似的书。此外，你通常不需要对前10本相似的书进行精确排名，比如100%、99%或95%的匹配度。这就是近似近邻（ANN）的思想。

让我们来了解一下为什么人工神经网络可以更有效地搜索。

近似最近邻(ANN)感觉像光速

ANN （Approximate Nearest Neighbors）对大数据进行预索引，方便快速搜索。在索引期间，构建数据结构以促进更快的查询。当您想为一个查询点找到近似的最近邻居时，您可以将该查询点提供给ANN算法。人工神经网络算法首先从数据集中识别一组可能接近查询点的候选数据点。使用预构建的数据结构选择候选对象。这一步骤大大减少了需要检查接近性的数据点的数量。在候选点被选中之前，ANN计算每个候选点与查询点之间的实际距离(如欧几里得距离、余弦相似度)。然后根据与查询点的距离/相似度对候选项进行排名。排名靠前的候选人作为近似近邻返回。在某些情况下，还可以设置距离阈值，只返回该阈值内的候选对象。人工神经网络背后的关键思想是，为了显著降低计算成本，它牺牲了找到绝对最近邻的保证。这些算法的目标是在计算效率和准确性之间取得平衡。

然而，在高维空间中，过去的实验表明ANN并不比KNN节省多少时间(见[4])。有几种创新的人工神经网络算法适用于高维空间。我将列出这些算法的字母表。您很快就会熟悉这些字母，并且可能更愿意在NLP社区中使用它们进行交流。让我们学习流行的最先进的算法。

最先进的快速搜索算法

这些不同的人工神经网络算法是不同的方法来形成数据结构，以实现有效的检索。有三种类型的算法：基于图的、基于哈希的和基于树的。

基于图的算法创建数据的图表示，其中每个数据点是一个节点，边表示数据点之间的接近性或相似性。最引人注目的是层次导航小世界图(HNSW)。

基于哈希的算法使用哈希函数将数据点映射到哈希码或桶。流行的算法包括：位置敏感哈希（LSH）、多索引哈希（MIH）和产品量化

基于树的算法将数据集划分为树状结构，以便快速搜索。流行的是kd树、球树和随机投影树（RP树）。对于低维空间（≤10），基于树的算法是非常有效的。

有几个流行的代码库:

1. Scikit-learn：它的NearestNeighbors类提供了一个简单的接口，可以使用LSH等技术进行精确和近似的最近邻搜索。
2. Hnswlib：它是HNSW的Python包装器。
3. FAISS：该库支持多种ANN算法，包括HNSW, IVFADC(带ADC量化的倒置文件)和IVFPQ(带产品量化的倒置文件)。
4. Annoy?(Approximate Nearest Neighbors Oh Yeah)：Annoy是一个c++库，也提供了Python接口。
5. NMSLIB(非度量空间库)：它是用c++编写的，并具有Python包装器。它可以执行HNSW、LSH、MIH或随机投影树等算法。

使用上述代码库，您可以超级快速地执行搜索查询。您还需要了解其他库的变体。这里我只提到其中的三个。第一个是PyNNDescent。PyNNDescent是一个Python库，用于基于NN-descent的搜索算法，它是LSH的一个变体。第二个是NearPy。它支持多个距离度量和哈希族。第三个是PyKDTree。PyKDTree是一个Python库，用于基于kd树的最近邻（KNN）搜索。虽然kd树更常用于精确搜索，但PyKDTree也可以通过一些启发式优化用于近似搜索。

此外，如果您询问哪些算法和库执行速度最好，您只需要了解**ANN- benchmark **库，专门为对人工神经网络搜索算法进行基准测试而设计。它提供了一个标准化的框架来评估算法，如Annoy，?FLANN，?scikit-learn?(LSHForest, KDTree, BallTree)，?PANNS，?NearPy，?KGraph，?NMSLIB(非度量空间库)，hnswlib，?RPForest，?FAISS，?nndescent，?PyNNDescent等等。

这不仅仅是最近邻在哪里，而是如何有效地找到他们。让我们学习第一个算法——HNSW。HNSW通常可以在几毫秒内从数百万个数据点中找到最近邻。

了解分层导航小世界图(HNSW)

HNSW是一种用于在高维空间中进行高效人工神经网络搜索的数据结构和算法。它是跳表和小世界图（SWG）结构的扩展，可以有效地找到近似的最近邻。如果我们先学习跳表和小世界图，学习HNSW就会很简单。

跳表是一种数据结构，用于维护一组已排序的元素，并允许进行高效的搜索、插入和删除操作。它是由William Pugh在1989年发明的。图(2)显示了数字[3、6、7、9、12、17、19、21、25、26]的排序链表。假设我们想找到目标19。当值小于目标时，我们向右移动。需要6步才能找到它。

排序链表

现在，如果列表的每个其他节点都有一个指向前面节点2的指针，如图3所示，可以将这些指针视为“高速公路”。数学规则是“当数值小于目标时向右移动”。需要4个步骤才能达到19。

跳表，其指针指向后面两个节点

这些高速公路加快了搜索速度。我们可以增加更多。现在，如果列表中每三个其他节点都有一个指向前面第三个节点的指针，如图(4)所示，那么只需要3步就可以到达19。

你可能会问，如何选择这些点作为”高速公路“？它们可以是预先确定的或随机选择的。这些节点的随机选择是Small World和NHSW中数据构建的重要步骤，我将在后面介绍。

跳表再升级，指向后面三个节点的指针

由跳表的思路延伸到Small World，我们来看看是怎么做的。

由跳表的思路延伸到Small World

小世界（small world）网络是一种特殊的网络，在这种网络中，你可以快速地联系到网络中的其他人或点。这有点像“凯文·培根的六度”(Six Degrees of Kevin Bacon)游戏，在这个游戏中，你可以通过一系列其他演员，在不到六个步骤的时间里，将任何演员与凯文·培根联系起来。

想象一下，你有一群朋友排成一个圆圈，如图5所示。每个朋友都与坐在他们旁边的人直接相连。我们称它为“原始圆”。

现在，这就是奇迹发生的地方。你可以随机选择将其中一些连接改变给圆圈中的其他人，就像图5中的红色连接线一样。这就像这些连接的“抢椅子”游戏。有人跳到另一把椅子上的几率用概率p表示。如果p很小，移动的人就不多，网络看起来就很像原来的圆圈。但如果p很大，很多人就会跳来跳去，网络就会变得有点混乱。当您选择正确的p值(不太小也不太大)时，红色连接是最优的。网络变成了一个小世界网络。你可以很快地从一个朋友转到另一个朋友(这就是“小世界”的特点)。

small-world网络

现在让我们学习从小世界网络到可导航小世界的过渡。

从小世界到HNSW

现在我们要扩展到高维空间。图中的每个节点都是一个高维向量。在高维空间中，搜索速度会变慢。这是不可避免的“维度的诅咒”。HNSW是一种高级数据结构，用于优化高维空间中的相似性搜索。

让我们看看HNSW如何构建图的层次结构。HNSW从图(6)中的第0层这样的基础图开始。它通常使用随机初始化数据点来构建。

HNSW

HNSW在层次结构中的基础层之上构造附加层。每个层将有更少的顶点和边的数量。可以把高层中的顶点看作是跳跃列表中访问“高速公路”的点。你也可以将这些顶点视为游戏“Six Degrees of Kevin Bacon”中的演员Kevin Bacon，其他顶点可以在不到6步的时间内连接到他。

一旦构建了上面的层次结构，数据点就被编入索引，并准备进行查询搜索。假设查询点是桃色数据点。为了找到一个近似最近的邻居，HNSW从入门级(第2层)开始，并通过层次结构向下遍历以找到最近的顶点。在遍历的每一步，算法检查从查询点到当前节点邻居的距离，然后选择距离最小的相邻节点作为下一个基本节点。查询点到最近邻居之间的距离是常用的度量，如欧几里得距离或余弦相似度。当满足某个停止条件(例如距离计算次数)时，搜索终止。

现在让我们看看HNSW是如何构建这些层的。

HNSW如何构建数据结构?

HNSW首先初始化一个空图作为数据结构的基础。该图表示一个接一个插入数据点的空间。HNSW将数据点组织成多层。每一层表示数据结构中不同级别的粒度。层数是预定义的，通常取决于数据的特征。

每个数据点随机分配到一个层。最高的一层用于最粗略的表示，随着层的向下移动，表示变得更精细。这个任务是用一个特定的概率分布来完成的，这个概率分布叫做指数衰减概率分布。这种分布使得数据点到达更高层的可能性大大降低。如果你还记得跳跃列表中随机选择的数据点作为“高速公路”，这里的一些数据点是随机选择到最高层的。在后面的代码示例中，我们将看到每层中的数据点数量，并且数据点的数量在更高层中呈指数级减少。

为了在每一层内有效地构建连接，HNSW使用贪婪搜索算法。它从顶层开始，试图将每个数据点连接到同一层内最近的邻居。一旦建立了一层中的连接，HNSW将使用连接点作为搜索的起点继续向下扩展到下一层。构建过程一直持续到处理完所有层，并且完全构建了数据结构。

让我们简单总结一下HNSW中数据结构的构造。让我也参考Malkov和Yashunin[3]中的符号，并在附录中解释HNSW算法。您可能会发现它们有助于更明确地理解HNSW的算法。HNSW声明一个空结构并逐个插入数据元素。它保持每个数据点每层最多有M个连接的属性，并且每个数据点的连接总数不超过最大值(Mmax)。在每一层中，HNSW找到与新数据点最近的K个邻居。然后，它根据距离更新候选数据点集和找到的最近邻居列表(W)。如果W中的数据点数量超过了动态候选列表(ef)的大小，则该函数从W中删除最远的数据点。

接下来，我将向您展示代码示例。该代码示例可通过此链接获得。

总结

我希望这篇文章能帮助你理解近似近邻(ANN)，以及它是如何提供高效搜索的。这篇文章解释了不同的人工神经网络算法，包括基于图的HNSW，基于哈希的LSH或产品量化，以及基于树的KD-Trees。这篇文章解释了HNSW如何构建其数据结构并逐个插入数据元素。代码链接演示了如何使用FAISS库构建用于查询搜索的HNSW。在下一篇文章“搜索像光速-(2)LSH”中，我将讨论基于哈希的算法。

附录

在Malkov和Yashunin[3]的论文中，算法1到5伪代码中提供了HNSW方法。伪代码给出了算法的具体定义。我将这些描述添加到伪代码中，因为一些读者可能会发现它们有助于理解HNSW。算法1、算法2、算法3、算法4中的一个用于完成数据结构。一旦数据结构完成，以后的任何查询搜索都只使用算法5。

• 算法1:“INSERT”函数构建数据结构
• 算法2:“SEARCH-LAYER”函数计算KNN并存储邻居
• 算法3:“SEARCH-NEIGHBORS-SIMPLE”是一种选择邻居的简单方法
• 算法4:“SELECT-NEIGHBORS-HEURISTIC”函数是一种更复杂的选择邻居的方法
• 算法5:“KNN-SEARCH”函数进行查询搜索

算法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

Algorithm 1: INSERT()

INSERT(hnsw, q, M, Mmax, 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, nor-
malization factor for level generation mL
Output: update hnsw inserting element q
1 W ← ? // list for the currently found nearest elements
2 ep ← get enter point for hnsw
3 L ← level of ep // top layer for hnsw
4 l ← ?-ln(unif(0..1))?mL? // new element’s level
5 for lc ← L … l+1
6 W ← SEARCH-LAYER(q, ep, ef=1, lc)
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) // alg. 3 or alg. 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 Mmax = Mmax0
15 eNewConn ← SELECT-NEIGHBORS(e, eConn, Mmax, lc)
// alg. 3 or alg. 4
16 set neighbourhood(e) at layer lc to eNewConn
17 ep ← W
18 if l > L
19 set enter point for hnsw to q

它在多层图中插入一个新元素q，保持每个元素每层最多有M个连接，并且每个元素的连接总数不超过Mmax的属性。该算法还保证连接元素之间的距离不大于某一最大距离，并且每层的连接数是均衡的。步骤如下:

1. W←?:初始化一个空列表W来存储当前找到的最近的元素。
2. ep←get enter point for hnsw:获取多层图hnsw的进入点(即起始点)。
3. L←ep的电平:获取进入点ep的电平。
4. l←ln(unitif(0..1))?mL?:为新元素q生成一个介于0和mL之间的随机级别，其中mL是级别生成的归一化因子。
5. for lc←L…L +1:循环从L到L +1的层。
6. W←SEARCH LAYER(q, ep, ef=1, lc):使用进入点ep和最大距离ef=1在lc层中搜索离q最近的元素。将找到的元素存储在列表W中。
7. ep←取W到q最近的元素:取W到q最近的元素。
8. for lc←min(L, L)…0:循环遍历从min(L, L)到0的层。
9. W←SEARCH LAYER(q, ep, efConstruction, lc):使用进入点ep和最大距离efConstruction搜索层lc中离q最近的元素。将找到的元素存储在列表W中。
10. neighbors←SELECT neighbors (q, W, M, lc):选择W到q最近的M个邻居，只考虑lc层的元素。
11. 在lc层添加邻居到q的双向连接:在lc层添加q与所选邻居之间的双向连接。
12. 对于每个e∈neighbors: //如果需要收缩连接
    对于q的每个邻居e，检查e的连接数是否超过Mmax。如果是这样，使用SELECT neighbors (e, eConn, Mmax, lc)选择一组新的邻居来收缩e的连接，其中eConn是e在lc层的当前连接集。
13. eNewConn←SELECT NEIGHBORS(e, eConn, Mmax, lc):为e选择一组新的邻居，只考虑lc层的元素，保证连接数不超过Mmax。
14. set neighborhood (e) at layer lc to eNewConn:将层lc的e的连接集更新为新的set eNewConn。
15. ep <- W:设置hnsw的进入点为q。
16. if 1 > L:将hnsw的起始点设为q，因为新元素q现在是图的一部分。
17. return hnsw:返回更新后的多层图hnsw。

算法2

它在HNSW数据结构上执行K近邻搜索，以查找特定层lc中与查询元素q最近的K个元素。然后，它根据查询元素q与候选元素C和e之间的距离更新候选元素C的集合和找到的最近邻居列表W。最后，如果W中的元素数量超过了动态候选列表ef的大小，则该函数删除从W到q最远的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Algorithm 2: SEARCH-LAYER()

SEARCH-LAYER(q, ep, ef, lc)
Input: query element q, enter points ep, number of nearest to q ele-
ments 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 │C│ > 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 ? v
11 v ← v ? e
12 f ← get furthest element from W to q
13 if distance(e, q) < distance(f, q) or │W│ < ef
14 C ← C ? e
15 W ← W ? e
16 if │W│ > ef
17 remove furthest element from W to q
18 return W

以下是上述代码的步骤:

1. 初始化变量v为当前的入口点ep。
2. 初始化集合C为当前候选集合。
3. 初始化一个空列表W来存储找到的最近邻。
4. 循环直到候选集合C中的所有元素都求值为止。
5. 从候选元素集合c中提取离查询元素q最近的元素c。
6. 获取从找到的最近邻W到查询元素q的列表中最远的元素f。
7. 如果c到q的距离大于f到q的距离:
8. 然后打破这个循环。
9. 对于lc层c邻域内的每个元素e:
10. 如果e不在访问元素v的集合中，则:
11. 将e添加到访问元素v的集合中。
12. 设f为从W到q的最远的元素。
13. 如果e和q之间的距离小于等于f和q之间的距离，或者W中的元素个数大于等于ef(动态候选列表的大小)，则:
14. 将候选集C更新为C∈e。
15. 将发现的最近邻居W的列表更新为W∈e。
16. 如果W中的元素个数大于等于ef，则:
17. 移除从W到q的最远的元素。
18. 返回找到的最近邻居W的列表。

算法3

这是一个简单的最近邻选择算法，它接受一个基本元素q、一组候选元素C和一些邻居M作为输入。它返回候选元素C集合中离q最近的M个元素。

1
2
3
4
5
6
7

Algorithm 3: SELECT-NEIGHBORS-SIMPLE()

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

步骤如下:

1. 初始化一个空集R来存储选中的邻居。
2. 初始化一个工作队列W来存储候选元素。
3. 如果设置了extendCandidates标志(即true)，则通过将C中每个元素的邻居添加到队列W来扩展候选列表。
4. 而W的大小大于0,R的大小小于M:
5. 从W到q中提取最近的元素e。
6. 如果e比R中的任何元素更接近q，把e加到R中。
7. 否则，将e添加到丢弃队列Wd中。
8. 如果设置了keepPrunedConnections标志(即true)，则从Wd添加一些丢弃的连接到R。
9. 返回R。

算法4

这是一个更复杂的最近邻选择算法，它接受一个基本元素q、一组候选元素C、若干个邻居M、一个层数lc和两个标志extendCandidates和keepPrunedConnections作为输入。它返回由启发式选择的M个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

Algorithm 4: SELECT-NEIGHBORS-HEURISTIC()

SELECT-NEIGHBORS-HEURISTIC(q, C, M, lc, extendCandidates, keep-
PrunedConnections)
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 ← ?
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 ← W ? eadj
8 Wd ← ? // queue for the discarded candidates
9 while │W│ > 0 and │R│< 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 Wd ← Wd ? e
15 if keepPrunedConnections // add some of the discarded
// connections from Wd
16 while │Wd│> 0 and │R│< M
17 R ← R ? extract nearest element from Wd to q
18 return R

步骤如下:

1. 初始化三个队列:R用于选择的邻居，W用于工作的候选，Wd用于丢弃的候选。
2. 设置R的大小为0,W的大小为C的大小。
3. 如果extendCandidates被设置(即，true):
4. 对于C中的每个元素e:
5. 对于第lc层e的每一个邻居eadj:
6. 如果eadj不在W中，则在W中添加它。
7. 而W的大小大于0,R的大小小于M:
8. 从W到q中提取最近的元素e。
9. 如果e比R中的任何元素更接近q，把e加到R中。
10. 否则，将e加到Wd。
11. 如果设置了keepPrunedConnections(即true):
12. 而Wd的大小大于0,R的大小小于M:
13. 从Wd到q中提取最近的元素e。
14. 如果e比R中的任何元素更接近q，就把e加到R中。
15. 返回R。

算法5

这个搜索算法与算法1基本相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Algorithm 5: K-NN-SEARCH()

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

步骤如下:

1. 初始化一个空集合W(当前最近元素的集合)，并将进入点ep设置为网络的顶层。
2. 设置进入点ep的水平为顶层L。
3. 对于每一层lc，从L到1(即从顶层到底层):
4. 使用查询元素q和当前最近的元素W搜索当前层，并将最近的元素添加到W中。
5. 将进入点ep设置为W到q最近的元素。
6. 使用查询元素q和当前最近的元素W搜索下一层，并将最近的元素添加到W中。
7. 返回W中最接近的K个元素作为输出。

引用

• [1]?Pugh, W. (1990). Skip lists: A probabilistic alternative to balanced trees.?Communications of the ACM, 33(6), 668–676. doi:10.1145/78973.78977. S2CID 207691558.
• [2]?Xiang Zhang, Junbo Zhao, & Yann LeCun. (2015). Character-level Convolutional Networks for Text Classification
• [3]?Yu. A. Malkov, & D. A. Yashunin. (2018). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs.
• [4] Aristides Gionis, Piotr Indyk, Rajeev Motwani, et al. 1999. Similarity search in high dimensions via hashing. In Vldb, Vol. 99. 518–529.