《大规模分布式计算深入解析》2.1 图索引基础:近邻图、导航结构与贪婪搜索

图搜索须区分前移、展开、边检查和首次算距;链上停点2是精确并列最近,另用局部陷阱解释贪婪搜索漏召回。

图里存的是什么

节点映射向量身份,邻接表给出可探索边。图可能有向;一次插入尝试双向连边后,邻居剪枝仍可能使方向不对称。图的导航能力来自可达路径和边的几何分布,不是只有平均度这个数字。

构造完整点对距离表可用N(N−1)/2次无向去重算距,N=6时15次。但这是穷举构图方法,不是所有近邻图都必须O(N²)的证明。近似构建、图搜索式插入和剪枝具有各自的成本与误差。

链例子中的停止也要算距

取0..7的一维相邻链,入口0,q=2.5,单候选贪婪搜索。0到1到2的距离依次缩小;为了知道邻居3不更好,需要计算d(q,3)=0.5。于是展开3个节点0/1/2,首次算距4个点0/1/2/3。

停点2和3都是真实最近邻,若采用距离相等按ID升序,Top1为2。这个例子不能被标为“非全局最近”。

真正的局部陷阱

三个点坐标0、3、1,边0↔3↔1,查询q=1,入口0。当前距离1,邻居3距离2,单候选贪婪不接受更差前进,于是停0;真实最近点1被中间更差的3挡住。提高候选宽度可能越过该桥,但效果取决图结构,不是固定线性召回公式。

四种计数

边检查计重复邻居,每个新发现点才算一次距离;候选弹出/展开数不等于所有已算距点,因为某点可能评估后被剪掉。结果只计可返回对象。跨层会重新算距时,应明确是每层调用总数还是去重点数。

HNSW高层帮助选入口,层零搜索维护候选前沿和结果堆。它解决的不是“只沿最优邻居单线走”这一种搜索。

架构与流程

flowchart TD
 E["入口点与当前最好结果"] --> N["检查邻接"]
 N --> D["未见邻居:计算距离"]
 D --> B{"单候选是否改善?"}
 B -->|是| MOVE["前移并继续展开"]
 MOVE --> N
 B -->|否| STOP["停止;刚才仍做了距离计算"]
 STOP --> CHECK["可能是精确最近,也可能是局部陷阱"]
 CHECK --> GT["必须与精确GT对照"]

实现与验证边界

模型提供链搜索的4次算距/3次展开和局部陷阱;小数据集与邻接显式给定。未从节点数推导真实大图时延。

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

一手资料

卷十三目录 · 系列导读

继续阅读

探索更多技术文章

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

全部文章 返回首页

「books」更多文章

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