arXiv:2501.13992v2 自动类型: replace-cross 摘要：层次可导航的小世界（HNSW）算法广泛用于近似最近邻（ANN）搜索，利用了可导航小世界图的原则。然而，该算法面临着一些局限性。首先是局部最优问题，这是由于算法的贪婪搜索策略所引起的，在每一步仅根据邻近性选择邻居，这通常导致集群断开连接。第二局限性是HNSW在高维数据集中难以实现对数复杂度，主要是由于每一层的完全遍历所导致的。为了克服这些局限性，我们提出了一种新颖的算法，该算法可以缓解局部最优和集群断开连接，同时提高构建速度，保持推理速度。第一个组件是基于LID的插入机制的双分支HNSW结构，允许从多个方向遍历，从而提高了离群节点的捕获能力、增强了集群连接性、加快了构建速度并减少了局部极小值的风险。第二个组件结合了一种桥梁构建技术，它绕过冗余的中间层，保持推理速度并弥补了双分支结构引入的额外计算成本。在各种基准测试和数据集上的实验表明，我们的算法在准确性和速度上均优于原始的HNSW。我们在计算机视觉（CV）和自然语言处理（NLP）六个数据集上进行了评估，在NLP任务中获得了18％的召回率提升，在CV任务中获得了高达30％的召回率提升，同时将构建时间减少了最多20％，并保持了推理速度。我们的算法没有表现出任何权衡。消融研究显示，基于LID的插入机制对性能的影响最大，其次是双分支结构和桥梁构建组件。