引用binarymax · 2022-07
“HNSW is not “the best” but it’s easy to understand and is quite effective.”
说明 HNSW 虽非最佳,但易懂且相当有效
多层邻近图索引,实现对数复杂度的近似最近邻搜索
论文提出 HNSW,一种完全基于图的近似 K 近邻搜索方法:增量式构建由嵌套子集的邻近图组成的多层结构,每个元素所在的最高层按指数衰减的概率随机选定。从上层开始搜索并利用尺度分离,性能优于 NSW 并带来对数复杂度的扩展;再加上选择邻居的启发式,能在高召回率和高度聚类数据上进一步提升。评测中它大幅超过此前的开源最先进纯向量方法,且与跳表相似,便于实现均衡的分布式版本。
评论者把它当作向量检索中易懂又相当有效的图索引的原始论文,也有人用它讨论非对称距离度量等细节。
“HNSW is not “the best” but it’s easy to understand and is quite effective.”
“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.”
“[1] Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs is I think the original paper that introduced the technique”