IVF家族与IVFFlat
IVF把库向量分配给粗量化器的列表;IVFFlat在列表里保留原向量,IVFPQ则使用压缩码。只有IVFFlat可以直接描述为“所选桶内按原向量精确算距”,不能把该性质推广给所有IVF变体。
典型训练先学习nlist个中心。插入时找最近中心并记录桶归属;查询时对中心路由,选nprobe个列表,再扫描列表内数据。训练、赋桶和查询是三个阶段,不能把每次查询重算全库赋桶的成本藏在查询计数之外。
本卷实际实现了什么
Ivf.train执行有限轮Lloyd:确定性初始化,最近中心分配,成员均值更新;空桶保留原中心,达到迭代上限或中心不再变化便结束。它不保证全局最优,也没有生产级采样、k-means++、并行和重新训练策略。
Ivf.Flat构建时保存向量和中心副本、预先赋桶;查询先缓存每个中心的距离并排序,再对选定桶成员做精确TopK。中心距离不在排序比较器中重复计算。候选不足K返回实际条数。
均匀桶例子的三本账
N=8000、nlist64,每桶125条。穷举中心路由先算64次;nprobe8扫描1000条,合计1064次;nprobe16扫描2000条,合计2064次。若改用近似粗量化器,中心访问与误差又有不同合同。
桶不均匀时扫描量必须对实际桶成员数求和,不能只取nprobe/nlist乘N。选择的桶集合嵌套、距离和选择规则保持不变时,扩大精确扫描范围不会减少可获得的真近邻;复杂压缩、过滤和预算交互不能直接沿用这个简单结论。
更新与退化
数据分布漂移会让训练中心不再合适,单桶热点也会增加尾延迟。重新训练会改变赋桶,需重新编码或迁移数据并受控切换。nprobe=nlist对IVFFlat意味着全库扫描,可接近精确基线;对压缩IVFPQ仍有量化误差,除非另有精排。
架构与流程
flowchart TD
TRAIN["有限Lloyd训练nlist中心"] --> BUILD["构建:预先赋桶并持有原向量"]
Q["查询q"] --> C["计算并缓存nlist个中心距离"]
C --> P["选择nprobe列表"]
BUILD --> SCAN["扫描所选列表实际成员"]
P --> SCAN
SCAN --> R["精确桶内TopK;中心/成员计数分开"]
实现与验证边界
模型实际执行有限训练、赋桶和查询,验证中心/成员/总数与精确结果。Milvus产品IVF索引未实测;当前原生场景不以HNSW替代它。
下载卷十三实验包
。Java 8入口为 lab.RunAll;本节对应 ivf.IvfSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。