数据充斥着世界，在海量多媒体内容中找到正确的信息变得越来越困难。想象一下，在百万个在线目录中寻找特定产品，或在庞大的数据库中搜索类似图片。这就是大规模相似性搜索发挥作用的地方，它提供了高效的方式来查找与给定查询相似的项目 - 无论是产品、图片、文本，甚至是一个复杂的想法。

在这篇文章中，我们将探讨大规模相似性搜索的基本概念，并介绍一些用于应对这一挑战的最强大的技术。我们将深入研究 Faiss 库，这是一个专为高效相似性搜索而设计的流行开源工具包，并探索基本的代码示例以帮助您入门。

为什么相似性搜索很重要？

人工智能和机器学习的兴起导致高维数据表示形式激增。这些表示形式通常称为嵌入，可以捕获数据点之间的复杂关系，从而实现强大的分析和理解。但在大型数据集中查找类似的嵌入是一项计算密集型任务。

相似性搜索正在彻底改变该领域的一个领域是检索增强生成 (RAG)。RAG 将传统信息检索与语言模型相结合，以提高生成文本的准确性和相关性。通过利用相似性搜索查找相关文档，RAG 模型可以访问更广泛的知识库并生成更具信息性和语境丰富的输出。

大规模相似性搜索的挑战

传统数据库和搜索引擎难以满足大规模相似性搜索的需求。它们依赖于结构化查询和索引方法，而这些方法并非为高维数据的动态特性而设计的。这时，专业技术就派上用场了。

Faiss 框架

Faiss是由 Facebook AI Research 开发的一款功能强大的库，专为高效相似性搜索而设计。它提供了一系列索引方法，每种方法都针对性能、准确性和内存使用量之间的不同权衡进行了优化。Faiss 还支持 GPU 加速，使其成为处理海量数据集的理想选择。

从基础开始

我们首先安装并导入必要的依赖项：

pip install faiss-cpu # for cpu
#pip install faiss-gpu # for gpu

import time
import faiss
import numpy as np

然后，我们定义一些常量：d向量的维数（128）、nb基向量的数量（10000）和nq查询向量的数量（100）。

# Dataset of vectors (10000 vectors of 128 dimensions)
d = 128  # dimension
nb = 10000  # number of base vectors
nq = 100  # number of query vectors

我们还初始化一个随机种子以获得可重现的结果。

np.random.seed(1234)  # For reproducibility

我们还生成两组随机向量，xb代表我们的基向量（10000 x 128）和xq代表我们的查询向量（100 x 128）。

# Random vectors
xb = np.random.random((nb, d)).astype('float32')
xq = np.random.random((nq, d)).astype('float32')

这些基本上就是我们的数据点。

1.分层可导航小世界（HNSW）

工作原理： HNSW 是一种基于图的索引方法，其中向量按小世界图的层进行组织。图中的每个节点（向量）都与其最近的邻居相连。在搜索过程中，算法会浏览图以快速收敛到最近的向量。

优点： HNSW 具有高精度和快速搜索时间，特别是对于高维数据集。

关键参数：

• M（每个节点的连接数）：控制图中每个节点所连接的邻居数。值越高，准确率越高，但内存消耗越大。
• efConstruction 和 efSearch：这些参数控制索引构建和搜索时的探索深度。值越高，搜索精度越高，但需要的计算量也越多。

IndexHNSWFlat VS IndexHNSWSQ (标量量化)

我们首先创建两个 HNSW 指数——HNSWFlat 和 HNSWSQ——来查看它们的表现。

HNSWFlat 是基本的 HNSW 实现：

# 1. HNSW index with Flat (no quantization)
index_hnswflat = faiss.IndexHNSWFlat(d, 32)  # 32 is the number of connections per layer

# Add the data
start = time.time()
index_hnswflat.add(xb)
indexing_time_hnswflat = time.time() - start

# Search with HNSWFlat
start = time.time()
D, I = index_hnswflat.search(xq, 5)  # Search 5 nearest neighbors
search_time_hnswflat = time.time() - start

而 HNSWSQ 则采用标量量化 (SQ) 来实现更快的索引。

# 2. HNSW with Scalar Quantization (SQ)
quantizer_sq = faiss.IndexScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)
index_hnswsq = faiss.IndexHNSWFlat(d, 32)

# Add the data
start = time.time()
index_hnswsq.add(xb)
indexing_time_hnswsq = time.time() - start

# Search with HNSWSQ
start = time.time()
D, I = index_hnswsq.search(xq, 5)
search_time_hnswsq = time.time() - start

这两个索引都使用“平面”存储方法，这意味着它们不会压缩原始向量。

print(f"HNSWFlat Indexing Time: {indexing_time_hnswflat:.4f} seconds")
print(f"HNSWFlat Search Time: {search_time_hnswflat:.4f} seconds")

print(f"HNSWSQ Indexing Time: {indexing_time_hnswsq:.4f} seconds")
print(f"HNSWSQ Search Time: {search_time_hnswsq:.4f} seconds")

与基于 IVF 的方法相比，这两种 HNSW 方法的索引速度都明显较慢，因为 HNSW 会构建邻居图，这在计算上非常耗时。HNSWSQ 比 HNSWFlat 稍快，因为标量量化 (SQ) 通过在索引过程中更紧凑地表示向量来降低向量的维数。

由于需要遍历图来查找最近邻，因此 HNSWFlat 和 HNSWSQ 的搜索时间都比基于 IVF 的方法略长。HNSW 以高精度而闻名，尤其是在高维空间中，但代价是索引速度较慢且搜索时间较长。

2. 倒排索引（IVF）

工作原理：倒排文件索引 (IVF) 是另一种常用的大型数据集相似性搜索方法。它将数据集划分为存储桶或“列表”，并且每个查询仅搜索存储桶的子集。

优点： IVF 的主要优点是与 HNSW 相比，其对内存的要求较低。

关键参数：

• nlist：簇（或桶）的数量。数字越大，精度越高，但索引时间越长。
• nprobe：查询过程中搜索的簇数。增加此参数会提高召回率，但会降低搜索速度。

没有乘积量化的 IndexIVFFlat 与有乘积量化的 IndexIVFPQ

IVFFlat 使用没有量化的平坦索引。

# Number of clusters (nlist)
nlist = 100

# 3. Flat index (no quantizer)
quantizer = faiss.IndexFlatL2(d)  # No quantization
index_ivfflat = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)

# Train the index
start = time.time()
index_ivfflat.train(xb)
index_ivfflat.add(xb)
indexing_time_ivfflat = time.time() - start

# Search with IVFFlat
index_ivfflat.nprobe = 10  # How many clusters to search
start = time.time()
D, I = index_ivfflat.search(xq, 5)  # Search 5 nearest neighbors
search_time_ivfflat = time.time() - start

而IVFPQ则采用了产品量化（PQ）来提高内存效率。

# Number of sub-vectors for PQ (m) and number of bits per sub-vector (nbits)
m = 8
nbits = 8

# 4. IVF with Product Quantization (PQ)
index_ivfpq = faiss.IndexIVFPQ(quantizer, d, nlist, m, nbits)

# Train the index
start = time.time()
index_ivfpq.train(xb)
index_ivfpq.add(xb)
indexing_time_ivfpq = time.time() - start

# Search with IVFPQ
index_ivfpq.nprobe = 10  # Adjust number of clusters to search
start = time.time()
D, I = index_ivfpq.search(xq, 5)  # Search 5 nearest neighbors
search_time_ivfpq = time.time() - start

关键思想是 IVF 将数据集划分为簇（桶），并且每个查询仅搜索这些桶的子集。我们将其设置nlist为 100，这意味着我们有 100 个簇。

print(f"IVFFlat Indexing Time: {indexing_time_ivfflat:.4f} seconds")
print(f"IVFFlat Search Time: {search_time_ivfflat:.4f} seconds")

print(f"IVFPQ Indexing Time: {indexing_time_ivfpq:.4f} seconds")
print(f"IVFPQ Search Time: {search_time_ivfpq:.4f} seconds")

与 IVFFlat 相比，IVFPQ 的索引时间明显更长。这是因为 IVFPQ 在初始聚类之后涉及额外的量化步骤。它应用乘积量化 (PQ)，这需要学习一个码本，将每个向量压缩为多个量化子向量。

由于搜索过程中需要解压缩并从量化表示中重建向量，因此 IVFPQ 的搜索时间略长。不过，这种差异很小，而且 IVFPQ 带来的内存效率通常值得额外的搜索时间。

3. 局部敏感哈希（LSH）

工作原理： LSH 将高维向量转换为低维“哈希”值。相似的向量更有可能共享相同的哈希值，因此可以通过关注包含相关哈希的存储桶来实现高效搜索。

优点： LSH 提供了一种快速且可扩展的相似性搜索方法，特别是对于大型数据集和高维空间。

关键参数：

• 哈希表数量：控制准确度和速度之间的平衡。哈希表数量越多，准确度越高，但搜索时间越长。
• 每个表的哈希函数数量：用于生成每个哈希值的哈希函数数量。IndexLSH

一种基于散列的方法，使用随机投影为每个向量创建散列值。

# 5. LSH
nbits = 16  # Number of bits for hash
index_lsh = faiss.IndexLSH(d, nbits)

# Add data to the index
start = time.time()
index_lsh.add(xb)
indexing_time_lsh = time.time() - start

# Search with LSH
start = time.time()
D, I = index_lsh.search(xq, 5)  # Search 5 nearest neighbors
search_time_lsh = time.time() - start

相似的向量更有可能共享相同的哈希值，因此可以通过关注包含相关哈希的存储桶来实现快速搜索。我们的哈希值为 16 位。

print(f"LSH Indexing Time: {indexing_time_lsh:.4f} seconds")
print(f"LSH Search Time: {search_time_lsh:.4f} seconds")

LSH 的索引速度极快，因为它仅根据随机投影将数据点散列到哈希桶中。它没有像 IVF 方法或 HNSW 那样的训练过程，因此索引几乎是即时的。

与 IVFFlat 和 HNSW 相比，LSH 搜索速度相对较慢，这是因为 LSH 具有随机性，可能需要搜索多个哈希桶才能找到最近的邻居。LSH 通常提供快速索引，但与 HNSW 或 IVFPQ 等更复杂的方法相比，可能会牺牲准确性和搜索速度。

参考：

https://medium.com/@ayoubkirouane3/introduction-to-large-scale-similarity-search-part-one-hnsw-ivf-lsh-677bf193ab07