虽然像HNSW这类基于图的方法构建精密的邻域图用于搜索，但倒排文件索引 (IVF) 方法采取不同的途径，借鉴了传统信息检索和聚类的原理。IVF将整个向量 (vector)空间划分为不同的区域，或称单元，并将搜索工作集中在少数相关区域，显著减少所需的距离计算次数。
IVF的核心是聚类。在索引构建阶段：
- 通常会从数据库向量中抽样得到一个有代表性的子集。
- 聚类算法，通常是k-均值，在此样本（或整个数据集）上运行，以确定k个聚类中心。这些中心点作为向量空间不同区域的代表。
- 然后扫描整个数据集。每个向量v被分配到其最近的中心点ci。这会生成k个“倒排列表”（或称桶、单元），每个列表Li包含与中心点ci最接近的所有数据点的标识符（以及可能向量本身）。
IVF索引的结构。数据库向量（圆形）被分配到其最近的中心点（菱形，C1-C3），形成倒排列表（L1-L3）。查询向量（星形）首先与中心点进行比较；然后，只搜索与最近中心点对应的列表（例如，如果nprobe=1，则搜索L2）。
当查询向量q到来时，搜索过程如下：
- 查询向量q与k个中心点进行比较。
- 确定与q最接近的
nprobe个中心点。nprobe是一个重要的调优参数 (parameter)，通常是一个小的整数（例如1、5、10）。
- 搜索范围仅限于这些
nprobe个中心点对应的倒排列表中的向量。
- 在这些选定的列表中，对查询q与这些列表中的向量进行更精确的距离计算（甚至进行精确的k-NN搜索），以找到最终的近似最近邻。
IVF的有效性取决于聚类的质量和nprobe的选择。如果中心点能很好地划分空间，只搜索少数列表会大幅剪枝搜索空间。然而，增加nprobe会提高找到真实最近邻的可能性（更高的召回率），但会增加搜索时间，因为需要扫描更多的列表。
IVF 变体：解决内存和速度问题
基本的IVF方法，通常称为IVFFlat，将完整的原始向量 (vector)存储在每个倒排列表中。虽然简单，但如果向量维度较高，它仍然可能占用大量内存，并且如果这些列表很大，在选定列表中的搜索可能会很慢。为缓解这些问题，IVF常与向量压缩技术结合使用，主要是乘积量化 (quantization)（PQ），本章稍后将详细介绍。
IVFPQ：IVF与乘积量化的结合
最常见且有效的一种变体是IVFPQ。它对基本IVF结构进行了如下修改：
- 索引构建： 在将向量分配到其最近的中心点后（与IVFFlat类似），每个列表中的向量使用乘积量化进行压缩。倒排列表中不存储完整向量，只存储紧凑的PQ编码。如果需要重新排序或检索，原始向量可能会存储在其他地方，但索引本身只包含编码。
- 搜索：
- 查询q仍然根据与原始中心点向量的距离找到
nprobe个最近的中心点。
- 在选定的列表Li中搜索时，距离计算在原始查询向量q与存储在这些列表中的数据库向量的压缩PQ编码之间进行。这被称为非对称距离计算（ADC）。它之所以“非对称”，是因为我们比较的是一个完整向量（查询）与编码向量（数据库项）。
- 使用PQ编码的ADC比计算完整向量之间的距离快得多，并且存储索引所需的内存少得多。
IVFPQ的优势很明显：
- 内存占用减少： PQ显著缩小了索引中存储向量的大小（例如，从数百个浮点数到数十个字节）。
- 列表中搜索更快： 使用PQ编码（ADC）计算距离在计算上比使用原始向量更经济。
然而，这会以牺牲准确性为代价。量化会引入近似误差。使用ADC计算的距离是对真实距离的估算。这意味着IVFPQ可能会遗漏一些IVFFlat能在探测到的列表中找到的真实最近邻。
IVFFlat与IVFPQ的选择
- IVFFlat： 当内存限制较少且需要更高准确性（在探测到的单元内）时更适合。如果PQ尚未成为流程的一部分，实现起来更简单。瓶颈仍然在于探测列表中完整向量距离计算的数量。
- IVFPQ： 对于内存使用是主要考虑因素的超大型数据集来说必不可少。由于ADC，在探测到的单元内提供了显著更快的搜索速度。主要权衡是PQ压缩引入的准确性损失。除了
k和nprobe之外，调整PQ参数 (parameter)（子量化器数量、每个子量化器的位数）也变得重要。
其他考虑
- IVFADC： 常与IVFPQ互换使用，尤其强调在列表内搜索时的非对称距离计算步骤。对称距离计算（SDC）则较不常见，其中查询向量在比较前也被量化，这甚至更快，但通常不如ADC精确。
- 训练： IVFFlat和IVFPQ都需要一个训练阶段，涉及k-均值聚类以找到初始中心点。这种训练需要一个有代表性的数据集，并且对于较大的k或大型数据集可能耗时。
- 参数调优： 选择最优中心点数量(k)和探测数量(
nprobe)非常重要。
- 较小的k会导致列表更少、更大。如果
nprobe较小，搜索可能会更快，但列表可能过大，不利于高效的内部搜索。
- 较大的k会导致许多小列表。查找最近的中心点需要更长时间，但在列表中搜索更快。需要更大的
nprobe来保持召回率。
nprobe直接控制着搜索速度和召回率之间的权衡。
IVF的多种形式，特别是IVFPQ，是一系列强大且广泛使用的ANN算法。与像HNSW这类基于图的方法相比，它们提供了一组不同的权衡，尤其擅长在内存受限的环境中运行，并通过像k和nprobe这样的参数提供可调的性能。了解它们如何划分空间以及选择性地压缩向量，对于构建大规模向量搜索系统非常重要。
