图里存的是什么
节点映射向量身份,邻接表给出可探索边。图可能有向;一次插入尝试双向连边后,邻居剪枝仍可能使方向不对称。图的导航能力来自可达路径和边的几何分布,不是只有平均度这个数字。
构造完整点对距离表可用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分别运行模型与原生入口,失败必须返回非零。模型通过不代表完整产品实现。
一手资料
继续阅读
探索更多技术文章
浏览归档,发现更多关于系统设计、工具链和工程实践的内容。