Vamana负责什么
Vamana构建可导航图,RobustPrune在候选中先选离中心最近的点,再删除被该邻居充分覆盖的候选,最多保留R个邻居。alpha控制几何约束,不能用“保留数组前R−1项再塞一个指定父节点”替代。
本卷以欧氏距离定义规则alpha·d(selected,candidate)≤d(center,candidate)。代码用平方距,因此比较alpha²·d²而非alpha·d²。候选ID必须来自点集,禁止注入不存在的keepId。
几何算例
中心p=(0,0),候选a=(1,0)、b=(0.7,0.9)、c=(0.4,2)、d=(2.2,0),alpha1。a先留下;b更接近a而被剪;c距a约2.09、大于距p约2.04,留下;d被a覆盖。结果为a/c。R只是上限,不保证一定填满。
完整Vamana还有搜索候选、图更新和构建轮次。本卷实现RobustPrune与小型图例,不把一个几何函数称为完整Vamana构建器。
DiskANN为什么不等于mmap BFS
经典DiskANN在内存持有压缩码用于候选评分,SSD持有节点的原向量、邻接等内容;缓存减少部分读,beam搜索让一批候选的IO有并行机会。最终对已读取的原向量有更精确的距离与结果处理。
搜索列表长度控制候选质量/工作量,IO beam宽度控制一轮读取并发,不是图出度R。访问20个节点也不能直接推导20次设备IO,缓存、节点布局、sector/page和请求合并都会影响结果。
失败与文件一致性
节点读取失败、索引文件损坏、超时、压缩码与图版本不匹配都需要明确处理。不能默默少读一部分后仍宣称完整TopK。本卷实际映射测试会拒绝错误文件头,但没有实现SSD异步调度、缓存策略、完整索引文件或故障恢复。
架构与流程
flowchart LR
Q["查询向量 q"] --> LUT["内存:PQ查询距离表"]
PQ["内存:库向量压缩码"] --> SCORE["候选近似评分"]
LUT --> SCORE
SCORE --> FRONT["搜索前沿:优先候选 / visited / beam宽度"]
FRONT --> CACHE{"候选节点数据在缓存?"}
CACHE -->|"是"| NODE["原向量与邻接表"]
CACHE -->|"否"| READ["提交有限并行的SSD读取"]
READ --> SSD["磁盘节点布局:向量、邻接、元数据"]
SSD -->|"读取完成"| NODE
NODE --> EXPAND["扩展邻居;更新候选近似分数"]
EXPAND --> SCORE
NODE --> EXACT["已读取原向量精确距离"]
EXACT --> RESULT["最终候选排序与结果"]
FAIL["读失败 / 超时 / 损坏"] -.-> POLICY["按实现拒绝、重试或失败返回"]
READ -.-> FAIL
实现与验证边界
几何剪枝原例与非法ID拒绝有真实断言;映射读取另在4.1验证。DiskANN分层图是原论文机制解释,没有部署DiskANN或测SSD吞吐,不把BFS当磁盘ANN实测。
下载卷十三实验包
。Java 8入口为 lab.RunAll;本节对应 diskann.DiskannSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。