虽然像HNSW这类基于图的方法构建精密的邻域图用于搜索,但倒排文件索引 (IVF) 方法采取不同的途径,借鉴了传统信息检索和聚类的原理。IVF将整个向量空间划分为不同的区域,或称单元,并将搜索工作集中在少数相关区域,显著减少所需的距离计算次数。IVF的核心是聚类。在索引构建阶段:通常会从数据库向量中抽样得到一个有代表性的子集。聚类算法,通常是k-均值,在此样本(或整个数据集)上运行,以确定$k$个聚类中心。这些中心点作为向量空间不同区域的代表。然后扫描整个数据集。每个向量$v$被分配到其最近的中心点$c_i$。这会生成$k$个“倒排列表”(或称桶、单元),每个列表$L_i$包含与中心点$c_i$最接近的所有数据点的标识符(以及可能向量本身)。digraph IVF { rankdir=LR; node [shape=circle, style=filled, fillcolor="#a5d8ff", label=""]; edge [arrowhead=none, color="#adb5bd"]; subgraph cluster_centroids { label = "中心点 (k)"; style=dashed; color="#adb5bd"; C1 [label="C1", shape=diamond, fillcolor="#ffec99"]; C2 [label="C2", shape=diamond, fillcolor="#ffec99"]; C3 [label="C3", shape=diamond, fillcolor="#ffec99"]; } subgraph cluster_list1 { label = "列表 L1"; style=dashed; color="#adb5bd"; V1_1; V1_2; V1_3; C1 -> V1_1; C1 -> V1_2; C1 -> V1_3; } subgraph cluster_list2 { label = "列表 L2"; style=dashed; color="#adb5bd"; V2_1; V2_2; V2_3; V2_4; C2 -> V2_1; C2 -> V2_2; C2 -> V2_3; C2 -> V2_4; } subgraph cluster_list3 { label = "列表 L3"; style=dashed; color="#adb5bd"; V3_1; V3_2; C3 -> V3_1; C3 -> V3_2; } Q [label="查询\n向量", shape=star, fillcolor="#ffc9c9"]; {rank=same; C1; C2; C3;} {rank=min; Q;} // 搜索路径 Q -> C2 [style=bold, color="#f03e3e", label="找到最近的\n中心点 (nprobe=1)", arrowhead=normal]; C2 -> V2_1 [style=bold, color="#f03e3e", arrowhead=normal, constraint=false, label=" 搜索\n 列表 L2"]; C2 -> V2_2 [style=bold, color="#f03e3e", arrowhead=normal, constraint=false]; C2 -> V2_3 [style=bold, color="#f03e3e", arrowhead=normal, constraint=false]; C2 -> V2_4 [style=bold, color="#f03e3e", arrowhead=normal, constraint=false]; }IVF索引的结构。数据库向量(圆形)被分配到其最近的中心点(菱形,C1-C3),形成倒排列表(L1-L3)。查询向量(星形)首先与中心点进行比较;然后,只搜索与最近中心点对应的列表(例如,如果nprobe=1,则搜索L2)。当查询向量$q$到来时,搜索过程如下:查询向量$q$与$k$个中心点进行比较。确定与$q$最接近的nprobe个中心点。nprobe是一个重要的调优参数,通常是一个小的整数(例如1、5、10)。搜索范围仅限于这些nprobe个中心点对应的倒排列表中的向量。在这些选定的列表中,对查询$q$与这些列表中的向量进行更精确的距离计算(甚至进行精确的k-NN搜索),以找到最终的近似最近邻。IVF的有效性取决于聚类的质量和nprobe的选择。如果中心点能很好地划分空间,只搜索少数列表会大幅剪枝搜索空间。然而,增加nprobe会提高找到真实最近邻的可能性(更高的召回率),但会增加搜索时间,因为需要扫描更多的列表。IVF 变体:解决内存和速度问题基本的IVF方法,通常称为IVFFlat,将完整的原始向量存储在每个倒排列表中。虽然简单,但如果向量维度较高,它仍然可能占用大量内存,并且如果这些列表很大,在选定列表中的搜索可能会很慢。为缓解这些问题,IVF常与向量压缩技术结合使用,主要是乘积量化(PQ),本章稍后将详细介绍。IVFPQ:IVF与乘积量化的结合最常见且有效的一种变体是IVFPQ。它对基本IVF结构进行了如下修改:索引构建: 在将向量分配到其最近的中心点后(与IVFFlat类似),每个列表中的向量使用乘积量化进行压缩。倒排列表中不存储完整向量,只存储紧凑的PQ编码。如果需要重新排序或检索,原始向量可能会存储在其他地方,但索引本身只包含编码。搜索:查询$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参数(子量化器数量、每个子量化器的位数)也变得重要。其他考虑IVFADC: 常与IVFPQ互换使用,尤其强调在列表内搜索时的非对称距离计算步骤。对称距离计算(SDC)则较不常见,其中查询向量在比较前也被量化,这甚至更快,但通常不如ADC精确。训练: IVFFlat和IVFPQ都需要一个训练阶段,涉及k-均值聚类以找到初始中心点。这种训练需要一个有代表性的数据集,并且对于较大的$k$或大型数据集可能耗时。参数调优: 选择最优中心点数量($k$)和探测数量(nprobe)非常重要。较小的$k$会导致列表更少、更大。如果nprobe较小,搜索可能会更快,但列表可能过大,不利于高效的内部搜索。较大的$k$会导致许多小列表。查找最近的中心点需要更长时间,但在列表中搜索更快。需要更大的nprobe来保持召回率。nprobe直接控制着搜索速度和召回率之间的权衡。IVF的多种形式,特别是IVFPQ,是一系列强大且广泛使用的ANN算法。与像HNSW这类基于图的方法相比,它们提供了一组不同的权衡,尤其擅长在内存受限的环境中运行,并通过像$k$和nprobe这样的参数提供可调的性能。了解它们如何划分空间以及选择性地压缩向量,对于构建大规模向量搜索系统非常重要。