《大规模分布式计算深入解析》1.1 最近邻问题域:kNN、范围查询与近邻语义

精确kNN是结果契约,不等同全量扫描;对照8次Flat算距与一维有序索引的2次精确算距,返回数、评估数和召回分别记录。

先定义问题,再选择访问路径

给定集合D、查询q、度量和K,精确kNN应返回按该度量排序的前K个有效对象。需要约定过滤、快照、并列结果与不足K的处理。范围查询则返回满足距离半径条件的对象集合;其结果条数不由K限制。

本卷使用平方L2作为Java默认距离。平方和与欧氏距离在非负区间排序相同,但半径r要比较平方距离≤r²,不能把r直接代入平方距离阈值。非零向量的余弦和内积排序规则另见1.2。

Flat基线的具体账本

向量位于(0,0)…(7,0),q=(0.6,0),K=3。欧氏距离前三为v1(0.4)、v0(0.6)、v2(1.4),平方距离为0.16、0.36、1.96。Flat逐条算距,8条就是8次;选择TopK可用小堆、部分选择或有序数组,不要求完整排序。

范围r=1返回v0/v1;若按主键输出则0/1,若按距离则1/0。结果契约应明确是否要求排序。

精确不意味着必须N次算距

把一维严格递增坐标预先建成有序索引,二分找到q的插入位置,只比较左右邻居0和1即可得精确Top1=v1。查询有二分比较成本,却只做2次距离计算;构建和校验有序性是另一个阶段。

这不是高维树索引必定高效的证明。维度和分布可能让剪枝退化到接近全扫描。它只说明“精确”约束结果,“Flat”指定实现,不能把两者混为一谈。

近似搜索的责任

图导航、部分桶探测或量化可以减少工作,也可能漏掉真近邻。比如近似结果{v1,v2,v3}对精确{v1,v0,v2}的集合召回@3是2/3。返回3条不表示访问3点,访问3点也不表示只做3次算距。记录返回ID、候选、算距和展开次数,才能解释误差从哪里产生。

架构与流程

flowchart TD
 C["度量/过滤/并列/K结果契约"] --> E["精确结果"]
 E --> FLAT["Flat:8条逐条算距"]
 E --> INDEX["一维有序索引:二分定位,左右2次算距"]
 C --> A["近似结果:索引预算与漏召回"]
 FLAT --> GT["同一精确真值"]
 INDEX --> GT
 A --> R["与GT比较;独立记返回/候选/算距"]

实现与验证边界

模型实现Flat精确TopK、一维SortedLine精确Top1与真实图搜索。相同8点例子固定于正文/用例;没有将一维索引性能推广到高维或Milvus内部实现。

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

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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