HNSW 剪枝优化：从贪婪连接到启发式邻居选择的核心剖析

HNSW 剪枝优化：从贪婪连接到启发式邻居选择的核心剖析引言分层可导航小世界（Hierarchical Navigable Small World，HNSW）算法是当前最有效的大规模近似最近邻搜索（ANN）索引之一。然而，在原始 HNSW 的构建阶段，每个新插入点的邻居选择采用的是简单的贪婪连接（greedy connection）：在候选集中选出距离最近的M个点作为邻居，而不考虑这些邻居之间的分布和连通性。这种方式可能导致部分区域连接过于稠密、高度重叠，造成索引膨胀、搜索效率下降，并增加内存占用。剪枝优化（pruning）正是在邻居选择环节引入更智能的策略——最具代表性的是启发式邻居选择（Heuristic Neighbor Selection），通过过滤掉“冗余”的候选邻居，构建出更稀疏、更高效的可导航图。本文将深入解析 HNSW 剪枝优化的原理、实现细节、性能特点，并给出源码级示例。1. 剪枝优化的核心思想在 HNSW 构建过程中，为节点q选择M个邻居时，基本步骤为：在图中执行多层搜索，得到候选集W（通常大小设为ef_construction）。从W中挑选最终的M