倒排文件索引 (IVF) 变体

虽然像HNSW这类基于图的方法构建精密的邻域图用于搜索，但倒排文件索引 (IVF) 方法采取不同的途径，借鉴了传统信息检索和聚类的原理。IVF将整个向量 (vector)空间划分为不同的区域，或称单元，并将搜索工作集中在少数相关区域，显著减少所需的距离计算次数。

IVF的核心是聚类。在索引构建阶段：

1. 通常会从数据库向量中抽样得到一个有代表性的子集。
2. 聚类算法，通常是k-均值，在此样本（或整个数据集）上运行，以确定$k$个聚类中心。这些中心点作为向量空间不同区域的代表。
3. 然后扫描整个数据集。每个向量$v$被分配到其最近的中心点$c_i$。这会生成$k$个“倒排列表”（或称桶、单元），每个列表$L_i$包含与中心点$c_i$最接近的所有数据点的标识符（以及可能向量本身）。

IVF索引的结构。数据库向量（圆形）被分配到其最近的中心点（菱形，C1-C3），形成倒排列表（L1-L3）。查询向量（星形）首先与中心点进行比较；然后，只搜索与最近中心点对应的列表（例如，如果nprobe=1，则搜索L2）。

当查询向量$q$到来时，搜索过程如下：

1. 查询向量$q$与$k$个中心点进行比较。
2. 确定与$q$最接近的nprobe个中心点。nprobe是一个重要的调优参数 (parameter)，通常是一个小的整数（例如1、5、10）。
3. 搜索范围仅限于这些nprobe个中心点对应的倒排列表中的向量。
4. 在这些选定的列表中，对查询$q$与这些列表中的向量进行更精确的距离计算（甚至进行精确的k-NN搜索），以找到最终的近似最近邻。

IVF的有效性取决于聚类的质量和nprobe的选择。如果中心点能很好地划分空间，只搜索少数列表会大幅剪枝搜索空间。然而，增加nprobe会提高找到真实最近邻的可能性（更高的召回率），但会增加搜索时间，因为需要扫描更多的列表。

IVF 变体：解决内存和速度问题

基本的IVF方法，通常称为IVFFlat，将完整的原始向量 (vector)存储在每个倒排列表中。虽然简单，但如果向量维度较高，它仍然可能占用大量内存，并且如果这些列表很大，在选定列表中的搜索可能会很慢。为缓解这些问题，IVF常与向量压缩技术结合使用，主要是乘积量化 (quantization)（PQ），本章稍后将详细介绍。

IVFPQ：IVF与乘积量化的结合

最常见且有效的一种变体是IVFPQ。它对基本IVF结构进行了如下修改：

1. 索引构建： 在将向量分配到其最近的中心点后（与IVFFlat类似），每个列表中的向量使用乘积量化进行压缩。倒排列表中不存储完整向量，只存储紧凑的PQ编码。如果需要重新排序或检索，原始向量可能会存储在其他地方，但索引本身只包含编码。
2. 搜索：
   • 查询$q$仍然根据与原始中心点向量的距离找到nprobe个最近的中心点。
   • 在选定的列表$L_i$中搜索时，距离计算在原始查询向量$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这样的参数提供可调的性能。了解它们如何划分空间以及选择性地压缩向量，对于构建大规模向量搜索系统非常重要。