新点在哪些层连边
先采样新点最高层L。从现有最高层入口下降到L之上,主要用于定位;从min(L,当前最高层)向0收集候选并选择邻居。层编号非负,不存在“层0及以下”的负层图。
新节点尝试与最多M个选定近邻建立双向邻接。对被连接的旧节点,如果加入后超过该层上限,则再次剪枝。hnswlib0.8.0典型设置maxM=M、maxM0=2M;本卷模型采用这个层预算,但不宣称所有实现都相同。
为什么不能只保留最近M
查询原点p=0,候选坐标1、1.1、−2,保留上限2。最近截断会取1和1.1;几何多样性规则先取1,再发现1.1更接近已选1而非p,于是跳过;−2与1相距3、大于它到p的距离2,因此可留下。结果1和−2覆盖两个方向,有利导航。
这是基于几何的邻居选择,而非Vamana的所有参数和多轮构建。本卷分别给出两者实现,避免同名pruning掩盖不同合同。
有向边数与“净增一条边”
两端邻接各记一个ID时,一次双向连接会增加两项。旧邻居剪枝可能只修改一端,最终图可出现不对称。因而“加2减1=净增1”只有先规定无向边还是邻接项才有意义。容量按分配槽算,实际边项按最终邻接遍历计,两者不可互换。
删除的结果资格和导航资格
链0→1→2,删除中间节点1后,查询2仍可经1到达2;1不返回,但其邻接还能参与导航。如果把“跳过墓碑”理解为不展开1,路径就被切断。真正删除、槽复用、重连和重建策略因实现而异,20%墓碑触发重建只是可选运维策略,不是HNSW算法常量。
教学索引保留墓碑和邻接,不做ID复用;重建应另创建新索引并受控切换。删除不能凭一个计数器验证,必须测试删除桥、入口已删、全删、结果不足及候选过滤。
架构与流程
flowchart TD
N["新点:采样最高层L"] --> U["高于L:贪婪选入口"]
U --> S["从min最高层到0逐层搜候选"]
S --> G["几何邻居选择;不只最近M"]
G --> LINK["尝试双向连边"]
LINK --> DEG{"旧节点超过该层容量?"}
DEG -->|是| PRUNE["重新几何剪枝"]
DEG -->|否| KEEP["保留邻接"]
D["删除ID"] --> T["结果排除;导航仍可穿过"]
实现与验证边界
模型实现几何选择、层容量约束与墓碑结果过滤,并通过受控删除桥。没有在线槽复用、锁或设备恢复。上游固定核心探针验证同样的删除导航区别,不能扩大为所有产品的删除策略。
下载卷十三实验包
。Java 8入口为 lab.RunAll;本节对应 hnsw.HnswSuite。按README分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。