图：kNN算法工作流程
在本文，我们将介绍一个基于Hierarchical Navigable Small World（HNSW）算法实现的HNSWlib的向量检索库。
01.
什么是向量检索
解读HNSWlib之前，我们需要对什么是向量检索先有一个基本的概念。
向量检索是信息检索中的一种常用方法，用于从大量非结构化数据集（图像、文档、音频等）中找到与给定查询最相似的信息。顾名思义，文档和查询都被表示为高维向量空间中具有特定维度的向量。向量的维度取决于用于转换文档和查询的Embedding模型。例如，如果我们使用“all-MiniLM-L6-v2”作为Embedding模型，每个查询或文档将获得384个维度的向量。
在查询时，Embedding模型会将查询内容，转化为文档中已有的语义维度，然后进行计算，相似含义的内容在向量空间中的位置更加靠近，然后返回其中最高相似性得分（或最短距离）的内容，这就是向量检索背后的逻辑。
图：2D向量空间中相似单词的向量嵌入
02.
什么是HNSW
近些年，为了优化kNN的检索性能，业内已经开发了各种索引算法，HNSW就是最有效的算法之一。
HNSW是一种基于图的高效向量检索算法。它依赖于两个关键概念：跳表（Skip List）和可导航小世界（NSW）图。
其中，跳表是一种概率数据结构，由多层链表组成，层次越高，链表中跳过的元素就越多。正如下面的可视化图，最低层包含了链表中的所有元素。随着我们向更高层移动，链表逐渐跳过越来越多的元素，所剩下的元素就越来越少。
图：跳表工作流程
假设我们需要从有3层和8个元素的原始链表中查找元素7。首先，我们从最高层开始，检查第一个元素是否低于7。如果是，那么我们检查第二个元素。如果第二个元素高于7，那么我们将第一个元素用作较低层的起点。接下来，我们在较低层做完全相同的事情，并逐渐下降到最低层以找到所需的元素。在许多元素上的跳过过程使得跳表在执行搜索操作时非常快。
理解了跳表的基本概念之后，我们再来看看NSW图。
NSW图中，每个节点（或称为顶点）都会与相似的节点相连，组成一张完整的NSW图。其检索的底层逻辑是贪婪路由搜索，从任意节点开始，检索起相邻节点中与其更加相似的节点，然后转移到该节点，过程循环往复，直到找到局部最小值，即当前节点比之前访问的任何节点都更接近查询向量，此时停止搜索。
图：NSW 图创建过程
HNSW算法，结合了跳表和NSW图的优势于一体。HNSW不仅仅是一个简单的二维图，而是由几层图所组成的多图层结构。与跳表概念类似，图的最低层包含所有元素，层越高，跳过的元素就越多。
在图创建过程中，HNSW首先为每个元素分配一个从0到 I 的随机数，其中 I 是一个元素在多层图中能存在的最大层。如果一个元素的 I 等于2，并且总层数为4，那么这个元素将从第0层一直存在到第2层，但不存在于第3层。
图：使用HNSW算法的向量检索
在向量检索过程中，HNSW算法首先选择最高层的任意节点，然后通过NSW图检索到局部最小值，紧接着，相同的流程在下一层重复，逐步逼近目标节点，直到找到最接近查询向量的节点。
通过这一方法，HNSW算法不必检索那些离查询点较远的相关度较低的元素，进而增加了检索的效率。这也导致了HNSW并不适用于精确匹配，因为HNSW在搜索过程中跳过了一些元素，当然，其他的近似最近邻（ANN）方法，如FAISS或ScaNN也是一样。
那么如何在不需要精确匹配结果，但仍然希望获得相对高效的召回时，我们要怎么办？我们可以调整HNSW的超参数：
M：NSW图中每个元素的边数。较高的M值通常会对应更好的搜索精度，但代价是更慢的索引构建时间。
efConstruction：构建索引时的动态候选列表大小。一般来说，候选队列越长，索引质量越好，索引构建时间也就会越长。
efSearch：搜索阶段的动态候选列表的大小。一般来说，efSearch越高，召回率越高，但是搜索过程会比较慢。
除了速度与精度的权衡之外，我们还需要注意图创建过程中的内存消耗。这是因为HNSW要求将整个数据集加载到RAM中，如果您的数据集太大而无法放入内存中，就会导致比较尴尬的情况发生。比如，M值越高，我们就需要分配越多存储资源用于每个元素相邻信息的存储。此外，随着元素和其相邻信息被添加到图中，内存需求会呈线性增长。因此，在图创建过程中，微调M和efConstruction至关重要，特别是在大规模应用中。
整体来说，HNSW具有对数复杂度O（log N）和高召回率，并支持动态更新，无需重建索引即可添加新数据。然而，与其他ANN算法相比，HNSWlib也具有更高的内存消耗，索引构建时间较慢，缺乏对元素删除的原生支持。
但与其他ANN方法相比，HNSW在大型数据集上的表现依然非常具有竞争力。
参考下面的GIST1M数据集（具有960维的1M向量）上的ANN基准测试，HNSW效果整体好于FAISS，Annoy，pgector等，特别是当需要高召回率时。排名上，其表现只在Milvus的Knowhere和Zilliz Cloud的Glass算法之后，获得了前三名的成绩。
图：GIST1M数据集的ANN基准测试结果
HNSWlib 是一个基于 C++ 的开源 HNSW 算法实现。用途上，HNSWlib 非常适合为向量检索用例构建简单场景，并不适合如1亿甚至数十亿数据点这样的复杂场景检索。
因为HNSWlib是一个功能有限的轻量级ANN库，会随着数据点的增长，因为内存消耗问题，导致出现扩展性瓶颈。
因此，在大规模应用中，使用像Milvus这样的向量数据库将是更好的选择。向量数据库作为一种成熟的解决方案，能够高效地存储大量数据并执行有效的向量检索。例如，Milvus支持云原生和多租户服务，允许用户从云上的多个用户存储、索引和检索数百万甚至数十亿个数据点。
当然，HNSWlib也可以被集成到Milvus这为代表的向量数据库中，接下来我们将展示这一过程。
03.
如何将HNSWlib与Milvus的集成
第一步，通过pip install安装HNSWlib：
pipinstallhnswlib
接下来，让我们创建100个虚拟数据点，每个数据点的维度为128。接下来，我们构建M为8，efConstruction为25的HNSW图。最后，我们计算查询数据点的最近邻。
importhnswlib
importnumpyasnp
importpickle
dim=128
num_elements=100
#Generatingsampledata
data=np.float32(np.random.random((num_elements,dim)))
ids=np.arange(num_elements)
#Generatingquerypoint
query=np.float32(np.random.random((1,dim)))
#Declaringindex
p=hnswlib.Index(space='l2',dim=dim)#possibleoptionsarel2,cosineorip
#Initializingindex-themaximumnumberofelementsshouldbeknownbeforehand
p.init_index(max_elements=num_elements,ef_construction=25,M=8)
#Elementinsertion(canbecalledseveraltimes):
p.add_items(data,ids)
#Controllingtherecallbysettingef:
p.set_ef(50)#efshouldalwaysbe>k
#Querydataset,k-numberoftheclosestelements(returns2numpyarrays)
labels,distances=p.knn_query(query,k=1)
这就是我们实现原生HNSWlib所要做的一切。
接下来，让我们看看如何在Milvus中使用HNSW集成。
使用Milvus的最简单方法是通过Milvus Lite（Milvus的轻量级版本，可以导入到您的Python应用程序中），我们可以使用pip install安装它。
!pipinstall-Upymilvus
!pipinstallpymilvus[model]
现在我们可以从创建集合并定义索引方法开始。首先，我们定义一个集合模式，指定HNSW作为索引方法，Milvus将自动在幕后使用HNSW。然后，我们可以开始将数据插入到集合中进行索引构建。
frompymilvusimportMilvusClient,DataType
frompymilvusimportmodel
client=MilvusClient("demo.db")
#1.Createschema
schema=MilvusClient.create_schema(
auto_id=False,
enable_dynamic_field=False,
)
#2.Addfieldstoschema
schema.add_field(field_name="id",datatype=DataType.INT64,is_primary=True)
schema.add_field(field_name="vector",datatype=DataType.FLOAT_VECTOR,dim=768)
schema.add_field(field_name="text",datatype=DataType.VARCHAR,max_length=200)
#3.Prepareindexparameters
index_params=client.prepare_index_params()
#4.Addindexes
index_params.add_index(
field_name="vector",
index_type="HNSW",
metric_type="L2"
)
#Createcollection
ifclient.has_collection(collection_name="demo_collection"):
client.drop_collection(collection_name="demo_collection")
client.create_collection(
collection_name="demo_collection",
schema=schema,
index_params=index_params
)
#Defineembeddingmodel
embedding_fn=model.DefaultEmbeddingFunction()
#Textdatatosearchfrom.
docs=[
"Artificialintelligencewasfoundedasanacademicdisciplinein1956.",
"AlanTuringwasthefirstpersontoconductsubstantialresearchinAI.",
"BorninMaidaVale,London,TuringwasraisedinsouthernEngland.",
]
#Transformtextdataintoembeddings
vectors=embedding_fn.encode_documents(docs)
data=[
{"id":i,"vector":vectors[i],"text":docs[i]}
foriinrange(len(vectors))
]
#InsertembeddingsintoMilvus
res=client.insert(collection_name="demo_collection",data=data)
Finally,ifwewanttoperformvectorsearch,wecandothefollowing:
SAMPLE_QUESTION="What'sAlanTuringachievement?"
query_vectors=embedding_fn.encode_queries([SAMPLE_QUESTION])
res=client.search(
collection_name="demo_collection",
data=query_vectors,
limit=1,
output_fields=["text"],
)
context=res[0][0]["entity"]["text"]
04.
结论
向量检索在需要准确度和速度的现代AI应用中非常重要。虽然kNN暴力搜索通过穷举搜索提供高度准确的结果，但其线性时间复杂度使其在大规模数据集上不切实际。
HNSW算法通过使用多层次图结构，在速度和准确性之间提供了创新的解决方案。通过结合跳表和NSW图，HNSW实现了快速、近似的搜索，可以有效处理海量数据集此外，通过微调超参数（如M、efConstruction和efSearch），我们可以根据每个应用所需的搜索速度、准确性和内存消耗这三者之间进行权衡优化。实际使用中，我们可以将HNSWlib集成到Milvus向量数据库优化我们的使用体验。
