The Faiss Library
FAIR, Meta
2024
摘要
向量数据库管理嵌入向量的大型集合。随着人工智能应用的快速增长，需要存储和索引的嵌入数量也在快速增长。Faiss库致力于向量相似性搜索，这是向量数据库的核心功能。Faiss是一个索引方法和相关原语的工具包，用于搜索、聚类、压缩和转换向量。本文首先介绍了矢量搜索的权衡空间，然后从结构、优化方法和接口等方面介绍了Faiss的设计原则。我们对库的关键特性进行基准测试，并讨论一些选定的应用程序，以突出其广泛的适用性。
介绍
提供矢量存储和搜索功能的工业数据库管理系统(DBMS)在过去几年中得到了广泛采用。这些数据库管理系统是传统数据库和近似最近邻搜索(ANNS)算法的结合。直到最近，后者主要用于特定的用例或研究中。
从实用的角度来看，在嵌入提取和向量搜索算法之间保持明确的角色分离有很多好处。两者都受嵌入距离的“embedding contract”约束:
-
嵌入提取器是现代系统中典型的神经网络，它经过训练，使嵌入之间的距离与要执行的任务保持一致。
-
向量索引旨在尽可能准确地在嵌入向量之间执行邻域搜索，而不是给出商定的距离度量的精确搜索结果。
Faiss是一个基于ANNS的工业级库。它被设计为既可以从简单的脚本中使用，也可以作为DBMS的构建块使用。与专注于单一索引方法的其他库相比，Faiss是一个包含索引方法的工具箱，这些方法通常涉及一系列组件(预处理、压缩、非穷举搜索等)。这是必要的：根据使用约束，最有效的索引方法是不同的。
总结：
- Faiss不提取特征，只索引通过不同机制提取的嵌入；
- Faiss不是一个服务，他是一个在本地机器上作为调用进程的一部分运行的函数；
- Faiss不是一个数据库，不提供并发写访问、负载均衡、分片和一致性；
Faiss的基本结构是索引。索引可以存储一些逐步添加到索引中的数据库向量。在搜索时，向索引提交查询向量。索引返回按欧几里得距离计算最接近查询向量的数据库向量。这个基本功能有很多变体：
- 可以返回k个最近邻，而不仅仅是最近邻；
- 不是固定数量的邻居，而是只返回一定范围内的向量；
- 几个向量可以并行搜索，以批处理模式：支持欧几里得距离以外的度量；
- 搜索的准确性可以用速度或内存来交换。
- 搜索可以使用CPU或GPU。
相关工作
索引方法
工业中最流行的方法之一是使用位置敏感哈希作为一种将嵌入压缩成紧凑代码的方法。特别是余弦草图产生二进制向量，使得在相应的汉明空间中，汉明距离是原始嵌入之间余弦相似度的估计量。这些草图的紧凑性使存储和搜索非常大的媒体内容数据库成为可能，而不需要存储原始嵌入。
在引入神经网络下降算法后，基于图的神经网络算法已经成为基于空间划分方法的可行替代方案。特别是HNSW，这是目前最流行的中型数据集索引方法，在HNSWlib中实现。
软件包
略
benchmarks和竞品
百万规模数据集的领先基准是ANNbenchmark，它现在比较了大约50种ANNS的实现。
该基准使用bigANN挑战进行了升级，该挑战包括6个数据集，每个数据集有10亿个向量。Faiss被用作挑战和来自Faiss的多个提交的基线。2023年的挑战赛规模较小(10M向量)，但任务更加复杂。例如，有一个过滤的轨道，Faiss是一个基线方法。
数据集
略
一个向量搜索库的性能轴
给定一组数据库向量 $\left\lbrace x_i, i=1 . . N\right\rbrace \subset \mathbb{R}^d$ 和一个查询向量 $q \in \mathbb{R}^d$，计算
\[n=\underset{n=1 . . N}{\operatorname{argmin}}\left\|q-x_n\right\|\]这可以通过迭代所有数据库向量的直接算法来计算：蛮力搜索。
一个稍微更一般更复杂的运算是计算 $q$ 的 $k$ 个近邻（Faiss的 search 方法给出的结果）：
Faiss 还有 range_search 方法，查找到查询的某个距离 $\varepsilon$ 内的所有元素：
Faiss中最常用的距离如下
这些措施之间存在许多关系。通过对查询和/或数据库向量进行预处理转换，可以使它们相等。
暴力搜索
高效地实现暴力搜索并非易事。它需要
- 一种有效的计算距离的方法；
- 对于 k 近邻搜索，需要一种有效的跟踪k个最小距离的方法。
Faiss中的距离计算可以通过直接距离计算来执行，或者当查询向量足够批量时，使用矩阵乘法分解来执行。
收集 top-k 最小距离通常通过CPU上的二进制堆或GPU上的排序网络来完成。对于较大的k值，使用储存库更有效：一个大小为k ‘ > k的无序结果缓冲区，当它溢出时将大小调整为k。
蛮力搜索给出了准确的结果。然而，对于大型、高维的数据集，这种方法变得很慢。在低维中，有分支定界方法可以产生精确的搜索结果。然而，在大的维度上，它们没有提供比暴力搜索更快的速度。
在这种情况下，我们不得不求助于近似最近邻搜索(ANNS)。
近似最近邻搜索的度量
使用ANNS，用户可以接受不完美的结果，这为新的解决方案设计空间打开了大门。数据库可以被预处理成一个索引结构，而不仅仅是作为一个普通的矩阵存储。
准确性度量
在人工神经网络中，准确度是用与精确搜索结果的差值来衡量的。
请注意，这是一个中间目标：端到端精度取决于
- 距离度量与项目匹配目标的相关性；
- ANNS的质量。
k个最近邻搜索的准确性通常用recall来评估，即输出结果中正确的向量个数的百分比。
对于 range_search，没看。
资源度量
搜索时间和内存使用是主要的约束条件。如果使用压缩，内存使用量可以小于原始向量。
索引可能需要存储训练数据，这在将任何向量添加到索引之前会产生恒定的内存开销。索引还会增加用于存储每个向量的内存开销。图索引就是这种情况，它需要为每个节点存储一个图。
建立索引的时间也是一个资源限制。它可以分解为一个训练时间，这是一个固定的成本，无论添加到索引中的向量的数量和每个向量的添加时间如何，都需要支付。
混合存储的设置，没看。
探索搜索时间设置
对于固定的索引，通常有一个或几个搜索时间超参数在速度和准确性之间进行权衡。我们可以只保留帕累托最优设置，即在给定精度下最快的设置，或者在给定时间预算下具有最高精度的设置。
讲了一下剪枝，略。
探索索引空间
Faiss包括一个基准测试框架，它探索索引设计空间，以找到最优地权衡准确性、内存使用和搜索时间的参数。超过一定规模后，搜索时间由查询向量与数据库向量之间的距离计算次数决定。Faiss中的非穷举搜索方法要么基于聚类，要么基于图探索。向量搜索的另一个限制因素是每个矢量的内存使用量。为了适应更多的向量，它们需要被压缩。
因此，采用剪枝和压缩相结合的方式构建Faiss索引，如下图所示。
微调
可以将快速但不准确的索引方法与较慢但更准确的搜索方法相结合。
那些方法都没看过，不看了。
压缩
未完待续