改进HNSW算法,提升搜索精度与速度,解决局部最优和连接断裂问题。
Dual-Branch HNSW Approach with Skip Bridges and LID-Driven Optimization
- 采用双分支结构与基于LID的插入机制,多方向遍历增强连通性。
- 引入跳桥技术减少层间冗余,推理速度保持不变,构建提速20%。
- 适用于高维数据场景,尤其在视觉与自然语言任务中表现优异。
Hierarchical Navigable Small World (HNSW) 算法广泛用于近似最近邻(ANN)搜索,利用可导航小世界图原理。然而其存在两个局限:一是贪婪搜索策略导致局部最优,引发簇间断连;二是高维数据下难以实现对数复杂度,因需逐层遍历。为此,本文提出一种新算法,缓解局部最优与断连问题,同时提升构建速度并保持推理效率。第一部分为基于LID的双分支HNSW结构,支持多路径遍历,提升异常点捕获能力,增强簇连通性,加快构建速度,降低局部极小风险。第二部分引入跳桥技术,跳过冗余中间层,维持推理性能,并抵消双分支带来的额外开销。在六个跨计算机视觉(CV)与自然语言处理(NLP)的数据集上实验表明,本算法在准确率与速度上均优于原始HNSW:NLP任务召回率提升18%,CV任务最高提升30%,构建时间减少最多20%,且未观察到性能权衡。消融实验显示,基于LID的插入影响最大,其次为双分支结构与跳桥机制。
原文摘要 · Abstract (English)
The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search, leveraging the principles of navigable small-world graphs. However, it faces some limitations. The first is the local optima problem, which arises from the algorithm's greedy search strategy, selecting neighbors based solely on proximity at each step. This often leads to cluster disconnections. The second limitation is that HNSW frequently fails to achieve logarithmic complexity, particularly in high-dimensional datasets, due to the exhaustive traversal through each layer. To address these limitations, we propose a novel algorithm that mitigates local optima and cluster disconnections while enhancing the construction speed, maintaining inference speed. The first component is a dual-branch HNSW structure with LID-based insertion mechanisms, enabling traversal from multiple directions. This improves outlier node capture, enhances cluster connectivity, accelerates construction speed and reduces the risk of local minima. The second component incorporates a bridge-building technique that bypasses redundant intermediate layers, maintaining inference and making up the additional computational overhead introduced by the dual-branch structure. Experiments on various benchmarks and datasets showed that our algorithm outperforms the original HNSW in both accuracy and speed. We evaluated six datasets across Computer Vision (CV), and Natural Language Processing (NLP), showing recall improvements of 18\% in NLP, and up to 30\% in CV tasks while reducing the construction time by up to 20\% and maintaining the inference speed. We did not observe any trade-offs in our algorithm. Ablation studies revealed that LID-based insertion had the greatest impact on performance, followed by the dual-branch structure and bridge-building components.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。