《大规模分布式计算深入解析》1.3 精确搜索与近似搜索:暴力、排序与误差预算

候选数不能推导固定召回;用相同C=4构造全命中和全漏,对单查询K=3的离散召回与多查询平均分别计算。

精确基线需要哪些成本

Flat对N条逐一计算距离,TopK选择的成本取决实现:有序长度K数组可给O(NK)比较上界,小堆常为O(NlogK),部分选择又有不同成本。N=8/K=3时24是特定有序数组的宽松比较上界,不是每次运行必然执行的次数,更不是所有精确索引的复杂度。

相同候选数可以得到完全不同的召回

沿1.1的精确集合G={1,0,2}。候选C1={1,0,2,7}覆盖3个真近邻,精排Top3后召回1;候选C2={3,4,5,6}覆盖0个,精排也无法补回,召回0。两者候选数都是4。

口径本例结果不能推出
候选数量4召回必为0.90
真近邻交集3或0相同预算保证相同质量
精排工作对实际候选重算总导航工作只有4次算距
单查询Recall@30、1/3、2/3或1单次恰为0.99

0.90、0.99可以是多查询平均质量目标,但需要查询集和实际命中来验收,不能作为由候选数4/6算出的“模型算术”。目标、观测和产品保证要分列。

误差的三个来源

第一,路由或图导航没访问真近邻;第二,压缩距离排序与原距离不同;第三,过滤/分页/局部TopK在中间截断。精排只能修正已经召回对象的距离排序,不能恢复不在候选集里的对象。

质量和速度要分别测

距离数降低不必然使端到端延迟同比降低:随机内存、读取原向量、分片RPC、排队与融合也会主导。公平比较应固定数据/查询/过滤/度量和质量目标,扫参数得到质量—延迟曲线,而不是强求不同算法相同数值的超参。

架构与流程

flowchart LR
 G["精确GT:1/0/2"] --> A["候选4条,含全部GT"]
 G --> B["候选4条,不含GT"]
 A --> RA["精排召回1"]
 B --> RB["精排召回0"]
 RA --> V["同候选数,不同质量"]
 RB --> V
 V --> M["多query实测;目标不等于观测"]

实现与验证边界

模型重现同C的两种交集;真实召回必须对同一查询的精确真值计算。ef16与ef256的结果一致率单独命名,不能当精确召回。

下载卷十三实验包 。Java 8入口为 lab.RunAll;本节对应 hnsw.HnswSuite / eval.EvalSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

浏览归档,发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「books」更多文章

  1. 《大规模分布式计算深入解析·向量数据库与 AI 检索内核》 · 目录与学习路径(45 篇)
  2. 《大规模分布式计算深入解析》15.3 自研向量引擎:可执行骨架与工程缺口
  3. 《大规模分布式计算深入解析》14.1 Milvus:组件架构、段管理与检索链路