HNSW

定义

HNSW(Hierarchical Navigable Small World,分层可导航小世界)是一种基于图的近似最近邻(ANN)搜索算法,由 Yury Malkov 与 Dmitry Yashunin 于 2016 年提出,是当前向量检索中综合表现最好的内存索引之一。

原理

HNSW 把向量组织成多层邻近图:底层包含全部节点,越往上节点越稀疏,结构类似跳表的分层思想。每个节点与若干近邻相连,构成"小世界"网络。查询时从顶层某入口点出发贪心地向更近的邻居移动,逐层下降,到底层后用宽度受限的贪心搜索(参数 efSearch)收集候选,返回最近的 k 个。插入时用类似过程为新节点选边,参数 M 控制每点连接数。

优缺点

优点:召回率与查询速度的权衡曲线优异,支持增量插入。缺点:内存占用高(需存全部向量与图结构),删除支持较弱,构建耗时。

应用

Faiss、Milvus、Qdrant、Weaviate、pgvector、Elasticsearch 等几乎所有向量检索系统都实现了 HNSW。