按年被提到
20162022 · 1 次2026
算法与数据结构›经典算法与数据结构·arXiv:1603.09320 · cs.DS

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

基于分层可导航小世界图的高效、鲁棒近似最近邻搜索
Yu. A. Malkov, D. A. Yashunin · 2016

多层邻近图索引,实现对数复杂度的近似最近邻搜索

开始阅读 ↗PDFalphaXiv 讨论
被提及 · 3 人首次 2022-07-21 · 最近 2024-09-05发表于 IEEE Transactions on Pattern Analysis and Machine Intelligence
3不同的人
3活跃月份
3讨论串
1,909被引(OpenAlex)

论文提出 HNSW,一种完全基于图的近似 K 近邻搜索方法:增量式构建由嵌套子集的邻近图组成的多层结构,每个元素所在的最高层按指数衰减的概率随机选定。从上层开始搜索并利用尺度分离,性能优于 NSW 并带来对数复杂度的扩展;再加上选择邻居的启发式,能在高召回率和高度聚类数据上进一步提升。评测中它大幅超过此前的开源最先进纯向量方法,且与跳表相似,便于实现均衡的分布式版本。

HN 为什么提它

评论者把它当作向量检索中易懂又相当有效的图索引的原始论文,也有人用它讨论非对称距离度量等细节。

奠基之作难度 3 / 5约 45 分钟经得起时间
读之前最好知道
1K 近邻搜索(k-NN)
2邻近图与小世界网络
3跳表(skip list)
4度量空间与距离度量

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
引用binarymax · 2022-07

“HNSW is not “the best” but it’s easy to understand and is quite effective.”

说明 HNSW 虽非最佳,但易懂且相当有效
Ask HN: What are some cool but obscure data structures you know about?原评论 ↗
引用bazzargh · 2023-05

“There's some discussion in the HNSW paper Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs of working with non-symmetric metrics but I haven't read further.”

指出论文讨论过 HNSW 处理非对称度量,自己没细读
Abusing Vector Search for Texts, Maps, and Chess ♟原评论 ↗
引用seanhunter · 2024-09

“[1] Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs is I think the original paper that introduced the technique”

认为这是最早提出 HNSW 技术的原始论文
Understanding Pgvector's HNSW Index Storage in Postgres原评论 ↗