用分层近邻图检索相似向量
HNSW 从稀疏上层快速定位区域,再在底层扩大候选搜索。
相关概念
工程问题#
语义检索需要从大量向量寻找相似项,逐个精确计算距离可能超过延迟预算。
实际实现#
Faiss 维护多层邻接关系;搜索先在高层贪心接近目标,再在底层探索候选,efSearch 控制搜索范围。
处理流程#
- 从最高层入口开始
- 沿邻边寻找更近节点
- 逐层下降到密集底层
- 扩展候选并返回近邻结果
源码片段#
固定版本 · 原文摘录faiss/impl/HNSW.cppv1.9.0 · L928–L945
928 // greedy search on upper levels929 storage_idx_t nearest = entry_point;930 float d_nearest = qdis(nearest);931932 for (int level = max_level; level >= 1; level--) {933 HNSWStats local_stats =934 greedy_update_nearest(*this, qdis, level, nearest, d_nearest);935 stats.combine(local_stats);936 }937938 int ef = std::max(params ? params->efSearch : efSearch, k);939 if (bounded_queue) { // this is the most common branch940 MinimaxHeap candidates(ef);941942 candidates.push(nearest, d_nearest);943944 search_from_candidates(945 *this, qdis, res, candidates, vt, stats, 0, 0, params);HNSW::search
从 entry_point 开始,在高层贪心更新最近节点,然后以该节点作为底层候选入口。ef 至少为 k,bounded_queue 分支用候选堆限制搜索范围。片段展示常见分支,后续代码另有无界候选队列路径;efSearch 是搜索宽度参数,不是精确召回保证。
CPPMIT
收益与取舍#
工程分析带来的收益
- 避免每次遍历全部向量
- 可通过搜索参数调整召回与延迟
付出的代价
- 图边需要额外内存,构建也有距离计算成本
- 近似搜索不保证找到真实最近邻
可比较的选择
IndexFlat穷举可作为精确基线;数据较小时,图构建和额外内存未必值得。
版本与适用范围#
以 Faiss v1.9.0 CPU HNSW 为基线;不同存储后端可组合不同压缩方法,不将 HNSW 等同于向量压缩。
参考来源#
源码、官方文档与原始论文相关实现与比较#
4 个相关案例借助计算依赖图与使用者计数,清理既不影响输出也无副作用的节点。
附源码片段 · 图处理与编译
Linux BPF 验证器的 check_cfg 使用显式指令栈执行非递归 DFS,检查跳转目标、可达性及控制流结构。
附源码片段 · 图处理与编译
LLVM 的 legacy 调用图 pass 管理器使用 Tarjan SCC 迭代器,将相互递归的函数作为一组,并按被调用方优先的顺序处理分组。
附源码片段 · 图处理与编译
Git 的拓扑历史遍历记录尚未输出的子提交数量;只有相关子提交都已处理,父提交才进入可输出集合。
附源码片段 · 图处理与编译