IVF (Inverted File) 索引算法介绍概述IVFInverted File是一种基于聚类思想的向量索引算法也称为倒排索引。该算法将向量空间划分为多个聚类或称为倒排文件每个聚类包含在特征空间中相近的向量。查询时算法首先将查询向量分配到最相关的几个聚类中然后只在这些聚类内部进行搜索从而大幅减少搜索空间。基本原理IVF算法的核心思想是分而治之空间划分将向量空间划分为多个不相交的子空间聚类聚类分配将每个向量分配到距离最近的聚类中心查询优化查询时只搜索最相关的几个聚类这种策略通过牺牲一定的准确性来换取查询性能的显著提升。算法架构聚类阶段聚类中心选择使用K-means等聚类算法确定聚类中心向量分配将每个向量分配到距离最近的聚类倒排文件构建为每个聚类维护一个向量列表查询阶段聚类选择找到查询向量最近的nprobe个聚类局部搜索只在选定的聚类内进行搜索结果合并合并各聚类的结果返回全局最优解数学表示给定向量集合V{v1,v2,...,vn}V \{v_1, v_2, ..., v_n\}V{v1​,v2​,...,vn​}聚类中心集合C{c1,c2,...,ck}C \{c_1, c_2, ..., c_k\}C{c1​,c2​,...,ck​}。聚类分配cluster(vi)arg⁡min⁡cj∈C∥vi−cj∥ \text{cluster}(v_i) \arg\min_{c_j \in C} \|v_i - c_j\|cluster(vi​)argcj​∈Cmin​∥vi​−cj​∥查询聚类选择selected_clusters(q){cj∈C∣∥q−cj∥ 是最小的nprobe个值之一} \text{selected\_clusters}(q) \{c_j \in C | \|q - c_j\| \text{ 是最小的nprobe个值之一}\}selected_clusters(q){cj​∈C∣∥q−cj​∥是最小的nprobe个值之一}搜索范围S(q){vi∈V∣cluster(vi)∈selected_clusters(q)} S(q) \{v_i \in V | \text{cluster}(v_i) \in \text{selected\_clusters}(q)\}S(q){vi​∈V∣cluster(vi​)∈selected_clusters(q)}时间复杂度分析构建时间O(n⋅d⋅k⋅I)O(n \cdot d \cdot k \cdot I)O(n⋅d⋅k⋅I)其中k是聚类数I是K-means迭代次数查询时间O(nprobe⋅nk⋅d)O(\text{nprobe} \cdot \frac{n}{k} \cdot d)O(nprobe⋅kn​⋅d)平均情况下空间复杂度O(n⋅dk⋅d)O(n \cdot d k \cdot d)O(n⋅dk⋅d)存储向量和聚类中心参数调优关键参数n_clusters聚类数量值越大每个聚类越小搜索精度越高值越小每个聚类越大查询速度越快典型值[4, 1024]通常选择n\sqrt{n}n​的数量级nprobe查询时搜索的聚类数量值越大搜索精度越高速度越慢值越小查询速度越快精度越低典型值[1, 20]通常设置为n_clusters\sqrt{\text{n\_clusters}}n_clusters​metric距离度量欧几里得距离适合稠密向量余弦距离适合稀疏向量或需要方向相似性的场景算法流程构建过程classIVFIndex:def__init__(self,n_clusters:int100,metric:streuclidean):self.n_clustersn_clusters self.metricmetric self.cluster_centersNoneself.inverted_lists[[]for_inrange(n_clusters)]deffit(self,vectors:np.ndarray):构建IVF索引# 使用K-means聚类fromsklearn.clusterimportKMeans kmeansKMeans(n_clustersself.n_clusters,max_iter20,tol1e-4)labelskmeans.fit_predict(vectors)self.cluster_centerskmeans.cluster_centers_# 构建倒排列表fori,vectorinenumerate(vectors):cluster_idlabels[i]self.inverted_lists[cluster_id].append((i,vector))defsearch(self,query:np.ndarray,k:int10,nprobe:int10):搜索最近邻# 计算与所有聚类中心的距离cluster_distancesnp.linalg.norm(self.cluster_centers-query,axis1)# 选择最近的nprobe个聚类selected_clustersnp.argpartition(cluster_distances,nprobe)[:nprobe]# 在选定的聚类中搜索candidates[]forcluster_idinselected_clusters:foridx,vectorinself.inverted_lists[cluster_id]:distancenp.linalg.norm(vector-query)candidates.append((distance,idx))# 返回距离最小的k个结果candidates.sort()indices[idxfor_,idxincandidates[:k]]distances[distfordist,_incandidates[:k]]returnindices,distances查询过程优化聚类距离预计算预先计算查询向量与聚类中心的距离候选合并使用优先队列高效合并多个聚类的结果提前终止当候选数量足够时提前终止搜索优缺点分析优点查询速度快通过聚类大幅减少搜索空间内存效率高相比图结构内存使用更可控易于理解算法直观实现简单可扩展性好适合分布式部署参数调优简单主要参数聚类数、nprobe影响相对直观缺点聚类边界问题向量可能位于聚类边界影响搜索精度聚类质量依赖性能受聚类质量影响较大参数敏感nprobe和聚类数的选择对性能影响显著动态更新困难插入新向量可能需要重新聚类适用场景中等规模数据10万到1000万向量的数据集平衡性能和精度需要较好的查询性能同时保持较高精度内存受限环境相比其他算法内存使用更可控分布式系统天然适合分布式部署高级变种IVFADC (IVF with Asymmetric Distance Computation)使用量化技术减少距离计算开销classIVFADCIndex(IVFIndex):def__init__(self,n_clusters:int100,n_bits:int8):super().__init__(n_clusters)self.n_bitsn_bits self.codebooksNoneself.compressed_vectorsNonedeffit(self,vectors:np.ndarray):构建IVFADC索引# 首先进行IVF聚类super().fit(vectors)# 为每个聚类构建码本self.codebooks[]self.compressed_vectors[]forcluster_idinrange(self.n_clusters):cluster_vectorsnp.array([vfor_,vinself.inverted_lists[cluster_id]])iflen(cluster_vectors)0:continue# 使用K-means构建码本n_centroids2**self.n_bits kmeansKMeans(n_clustersn_centroids,max_iter10)kmeans.fit(cluster_vectors)self.codebooks.append(kmeans.cluster_centers_)# 压缩向量compressed[]forvectorincluster_vectors:distancesnp.linalg.norm(kmeans.cluster_centers_-vector,axis1)codenp.argmin(distances)compressed.append(code)self.compressed_vectors.append(compressed)Multi-probe IVF通过智能选择更多聚类来提升精度classMultiProbeIVFIndex(IVFIndex):defsearch(self,query:np.ndarray,k:int10,nprobe:int10):多probe搜索# 计算与聚类中心的距离cluster_distancesnp.linalg.norm(self.cluster_centers-query,axis1)# 选择距离排序考虑聚类间的相关性selected_clustersself._select_clusters_smart(cluster_distances,nprobe)# 在选定的聚类中搜索candidates[]forcluster_idinselected_clusters:# 使用ADC加速距离计算foridx,vectorinself.inverted_lists[cluster_id]:distancenp.linalg.norm(vector-query)candidates.append((distance,idx))# 返回结果candidates.sort()indices[idxfor_,idxincandidates[:k]]distances[distfordist,_incandidates[:k]]returnindices,distances与其他算法的比较算法查询时间准确性内存使用构建时间FLATO(n⋅d)O(n \cdot d)O(n⋅d)100%O(n⋅d)O(n \cdot d)O(n⋅d)O(1)O(1)O(1)HNSWO(log⁡n⋅M⋅d)O(\log n \cdot M \cdot d)O(logn⋅M⋅d)95-99%O(n⋅log⁡n⋅M)O(n \cdot \log n \cdot M)O(n⋅logn⋅M)O(n⋅log⁡n⋅M⋅d)O(n \cdot \log n \cdot M \cdot d)O(n⋅logn⋅M⋅d)IVFO(nprobe⋅nk⋅d)O(\text{nprobe} \cdot \frac{n}{k} \cdot d)O(nprobe⋅kn​⋅d)90-95%O(n⋅dk⋅d)O(n \cdot d k \cdot d)O(n⋅dk⋅d)O(n⋅d⋅k⋅I)O(n \cdot d \cdot k \cdot I)O(n⋅d⋅k⋅I)LSHO(L⋅k⋅d)O(L \cdot k \cdot d)O(L⋅k⋅d)80-90%O(n⋅L⋅k)O(n \cdot L \cdot k)O(n⋅L⋅k)O(n⋅d)O(n \cdot d)O(n⋅d)性能优化并行聚类使用并行K-means加速构建增量更新支持增量式聚类更新缓存优化缓存热点聚类数据量化技术结合ADC减少内存和计算开销总结IVF算法通过空间划分的思想在向量相似性搜索中实现了性能与精度的良好平衡。它简单直观的实现方式、可控的内存使用以及良好的查询性能使其成为向量数据库领域的重要索引算法。尽管在边界处理和动态更新方面存在一些挑战但通过结合量化技术和多probe策略IVF算法在实际应用中表现出色特别是在中等规模数据集的场景下。