[论文翻译]高效且鲁棒的基于分层导航小世界图的近似最近邻搜索

Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs 高效且鲁棒的基于分层导航小世界图的近似最近邻搜索 Yu. A. Malkov, D. A. Yashunin Yu. A. Malkov, D. A. Yashunin Abstract — We present a new approach for the approximate K-nearest... 摘要 — 我们提出了一种基于可控层次结构的可导航小世界图 (Hierarchical NSW，HNSW) 的近似K近邻搜索新方法。该方案完全基于图结构，无需依赖大多数邻近图技术在粗搜索阶段常用的额外搜索结构。分层NSW通过渐进方式构建多层结构，该结构由存储元素嵌套子集的层次化邻近图 (层) 集合构成。元素所在最高层数采用指数衰减概率分布进行随机选择。这种方法既能生成与先前研究的可导航小世界 (NSW) 结构相似的图，又能实现按特征距离尺度分离的链接。从顶层开始搜索并结合尺度分离特性，使得该方案相比NSW具有性能提升，并能实现对数级复杂度。额外采用邻近图邻居选择启发式方法，可显著提升高召回率和高聚类数据场景下的性能。评估结果表明，所提出的通用度量空间搜索索引能够大幅超越先前开源的纯向量最优方案。该算法与跳表结构的相似性使其能够直接实现平衡分布式部署。