像光速一样搜索——HNSW算法介绍

本文是一篇英文翻译转载文章，主要介绍了HNSW算法。

原文链接：https://dataman-ai.medium.com/search-like-light-speed-1-hnsw-c5b0d4665926

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

图 (1)：文字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），基于树的算法是非常有效的。

有几个流行的代码库:

Scikit-learn：它的NearestNeighbors类提供了一个简单的接口，可以使用LSH等技术进行精确和近似的最近邻搜索。
Hnswlib：它是HNSW的Python包装器。
FAISS：该库支持多种ANN算法，包括HNSW, IVFADC(带ADC量化的倒置文件)和IVFPQ(带产品量化的倒置文件)。
Annoy (Approximate Nearest Neighbors Oh Yeah)：Annoy是一个c++库，也提供了Python接口。
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): 排序链表

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

图 (3): 跳表，其指针指向后面两个节点

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

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

图 (4): 跳表再升级，指向后面三个节点的指针

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

由跳表的思路延伸到Small World

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

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

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

图 (5): small-world网络

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

从小世界到HNSW

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

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

图 (6): 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中删除最远的数据点。

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

代码示例

接下来，让我们使用库FAISS执行HNSW搜索。我将使用NLP中包含新闻文章的流行数据集。然后，我使用“SentenceTransformer”执行Embeddings。然后，我将向您展示如何使用HNSW通过查询搜索类似的文章。

Data

总检察长的新闻文章语料库由[A.]Gulli](http://groups.di.unipi.it/~gulli/AG_corpus_of_news_articles.html)，是一个从2000多个新闻来源收集100多万篇新闻文章的大型网站。Zhang、Zhao和LeCun在论文中构建了一个较小的集合，其中采样了“世界”、“体育”、“商业”和“科学”等新闻文章，并将其用作文本分类基准。这个数据集“ag_news”已经成为一个经常使用的数据集，可以在Kaggle、PyTorch、Huggingface和Tensorflow中使用。让我们下载[数据从Kaggle](https://www.kaggle.com/datasets/amananandrai/ag-news-classification-dataset)。训练样本和测试样本分别有12万篇和7600篇新闻文章。

import pandas as pd
import numpy as np
import faiss
pd.set_option('display.max_colwidth', -1)
path = "/content/gdrive/My Drive/data"
train = pd.read_csv(path + "/gensim/ag_news_train.csv")
print(train.shape)
print(train.columns)
train['Description'][0:5]

输出形状为(120000,3)，列为[‘ Class Index ‘， ‘ Title ‘， ‘ Description ‘]。我们对“描述”栏感兴趣。以下是排名前五的记录。

路透社——卖空者，华尔街日益减少的\band极端愤世嫉俗者，又看到了绿色
路透——私人投资公司凯雷投资集团(\which)以在国防工业投资时机恰当、偶尔引发争议而闻名，该公司已悄然将赌注押在了市场的另一个领域
路透社——油价飙升，加上对\about经济和盈利前景的担忧，预计将在下周\summer经济低迷的深度\hang拖累股市
路透社——一位石油官员周六表示，在\intelligence显示反叛民兵可能袭击\infrastructure后，当局已经停止了伊拉克南部主要管道\flows的石油出口
法新社——在距离美国总统大选仅剩三个月的时间里，世界油价不断刷新纪录，人们的钱包越来越紧，这给经济带来了新的威胁

数据嵌入

出于说明的目的，我只使用10,000条记录进行Embeddings。

1	sentences = train['Description'][0:10000]

您需要pip安装“sentence_transformers”库。

1 2	!pip install sentence_transformers from sentence_transformers import SentenceTransformer

然后让我们使用预训练模型“bert-base-nli-mean-tokens”来声明模型。在本页上有许多预先训练好的模型。

1	model = SentenceTransformer('bert-base-nli-mean-tokens')

然后我们将“句子”编码为“sentence_embeddings”。

1
2
3

sentence_embeddings = model.encode(sentences)
print(sentence_embeddings.shape)
sentence_embeddings[0:5]

输出是10,000个列表。每个列表或向量的维数为768。下面是前5个Embeddings的输出。

array([[-0.26105028, 0.8585296 , 0.03941074, …, 1.0689917 , 1.1770816 , -0.74388623], [-0.2222097 , -0.03594436, 0.5209106 , …, 0.15727971, -0.3867779 , 0.49948674], [-0.3001758 , -0.41582862, 0.86036515, …, -0.6246218 , 0.52692914, -0.36817163], [ 0.3295024 , 0.22334357, 0.30229023, …, -0.41823167, 0.01728885, -0.05920589], [-0.22277102, 0.7840586 , 0.2004052 , …, -0.9121561 , 0.2918987 , -0.12284964]], dtype=float32)

这有助于保存Embeddings以备将来使用。

1 2	with open(path + '/AG_news.npy', 'wb') as file: np.save(file, sentence_embeddings)

在上面的代码中，我使用了“npy”文件扩展名，这是NumPy数组文件的常规扩展名。下面是加载数据的代码:

1 2	with open (path + '/AG_news.npy', 'rb') as f: sentence_embeddings = np.load(f, allow_pickle=True)

有了这些Embeddings，我们就可以在HNSW数据结构中组织它们了。

使用FAISS构建NHSW数据结构索引

您需要像下面这样pip安装FAISS库:

1	!pip install faiss-cpu --no-cache

我将使用HNSWFlat(dim, m)类来构建HNSW。它需要预先确定的参数dim表示向量的维数，m表示数据元素与其他元素连接的边数。

import faiss
m = 32
dim = 768
index = faiss.IndexHNSWFlat(dim, m)

如前所述，HNSW指数的创建分为两个不同的阶段。在初始阶段，该算法采用概率分布来预测引入新数据节点的最上层。在接下来的阶段，收集每个数据点的最近邻居，然后用一个表示为m的值进行修剪(在我们的例子中是m=16)。整个过程是迭代的，从插入层开始，一直到底层。

HNSW中有两个重要参数“efConstruction”和“efSearch”。这两个参数控制着索引结构构建的效率和有效性。它们帮助您在HNSW索引结构中的索引构建和最近邻搜索操作的速度和质量之间取得平衡。

efConstruction:该参数用于HNSW索引的构建。它控制了构建索引结构的速度和结构质量之间的权衡。” efConstruction “值决定了在构建阶段要考虑多少候选项目。较高的“efConstruction”值将产生更准确的索引结构，但也会使构建过程变慢。
efSearch:该参数用于在HNSW索引中查找查询点的最近邻居。“efSearch”值控制搜索速度和搜索质量之间的权衡。较高的“efSearch”值将导致更准确和详尽的搜索，但也会更慢。我们将“efConstruction”和“efSearch”分别设置为40和16:

1 2	index.hnsw.efConstruction = 40 index.hnsw.efSearch = 16

我们已经声明了上面的数据结构。现在我们准备将数据“sentence_embeddings”一个接一个地插入到数据结构中:

1	index.add(sentence_embeddings)

一旦完成，我们可以检查HNSW数据结构中有多少数据元素:

1	index.ntotal

输出为10000。它是“sentence_embeddings”中的数据点数。接下来，HNSW建造了多少层?让我们来检查最大级别:

1 2	# the HNSW index starts with no levels index.hnsw.max_level

最高级别为2.0。这意味着有第0层，第1层和第2层。接下来，您可能想知道每层中数据元素的数量。让我们来看看:

1 2	levels = faiss.vector_to_array(index.hnsw.levels) np.bincount(levels)

输出为array([0,9713,280,7])。“0”没有意义，你可以忽略它。它说第0层有9713个数据元素，第1层有280个元素，第2层只有7个元素。注意，9713 + 280 + 7 = 10000。您是否发现，较高层的数据元素数量比前几层呈指数级减少?这是因为数据元素的层分配采用指数衰减概率分布。

FAISS为HNSW搜索示例

假设我们的搜索查询是“经济繁荣与股市（economic booming and stock market）”。我们希望找到与我们的搜索查询相关的文章。我们将首先嵌入搜索查询:

1	qry1 = model.encode(["economic booming and stock market"])

使用代码index.search()，搜索过程非常简单。这里k是最近邻居的个数。我们将其设置为5以返回5个邻居。index.search()函数返回两个值” d “和” I “。

“d”:查询向量与k个最近邻居之间的距离列表。默认的距离度量是欧几里得距离。
“I”:它是索引中k个最近邻居的位置对应的索引列表。这些索引可用于查找数据集中的实际数据点。

%%time
k=5
d, I = index.search(qry1, k)
print(I)
print(d)

索引列表的输出是[[1467 4838 4464 7461 8299]]。我们将使用这些索引打印出搜索结果。

注意，我使用“%%time”来度量执行时间。它输出

*CPU时间:user: 5.57 ms, sys: 5µs, total: 5.58 ms

这意味着搜索只需要几毫秒。这确实是令人难以置信的快!

距离输出列表为:[[158.19066 163.69077 164.47517 164.64172 164.64172]]

1 2	for i in I[0]: print(train['Description'][i])

输出：

‘Rising oil prices are expected to hit China’s growth rate this year.’

‘Developing countries are starting to flex their financial muscles and invest overseas.

‘The Tehran Stock Exchange has performed magnificently, but the market’s list of risks is outsized.’

‘Federal Express raised its earnings forecast, citing strong demand for its international express, ground and less-than-truckload services.’

‘Federal Express raised its earnings forecast, citing strong demand for its international express, ground and less-than-truckload services.’ (Our data have duplications)

这些文章都是关于经济和股票市场的新闻。搜索速度以毫秒计非常快。这不仅仅是结果在哪里的问题，而是如何快速得到结果的问题，不是吗?

您可以通过此链接下载笔记本进行上述搜索。

总结

我希望这篇文章能帮助你理解近似近邻(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开始。

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的属性。该算法还保证连接元素之间的距离不大于某一最大距离，并且每层的连接数是均衡的。步骤如下:

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

让我们看看算法2。

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

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

以下是上述代码的步骤:

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

算法3.

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

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

步骤如下:

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

让我们看看算法4。

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

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

步骤如下:

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

最后，让我们看看算法5。

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

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

步骤如下:

初始化一个空集合W(当前最近元素的集合)，并将进入点ep设置为网络的顶层。
设置进入点ep的水平为顶层L。
对于每一层lc，从L到1(即从顶层到底层):
使用查询元素q和当前最近的元素W搜索当前层，并将最近的元素添加到W中。
将进入点ep设置为W到q最近的元素。
使用查询元素q和当前最近的元素W搜索下一层，并将最近的元素添加到W中。
返回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.

Update: 2024-01-26

我们的TorchV Bot产品目前已经开始试用了，详情可以点击：https://www.luxiangdong.com/2024/01/25/lanuch-1
目前只接受企业用户试用，需要您填写一些信息，必要信息如下：

邮箱：用来接收地址和账号
如何称呼您：
所服务的公司：
您的职位：

当然，如果您可以告诉我们您的使用场景，我们将更加感激！
对了，可以发送到yuanwai@mengjia.net
另外，也可以直接加我微信（lxdhdgss）联系我。