Paper Type
Complete
Abstract
The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search but suffers from local optima, frequently fails to achieve logarithmic complexity and inefficiencies in high-dimensional spaces. We propose a novel algorithm that enhances search accuracy and speed. Our approach introduces a dual-branch HNSW structure with LID-based insertion, improving cluster connectivity and mitigating local minima. Additionally, we incorporate skip-bridge connections, bypassing redundant layers to accelerate inference. Experiments on 12 datasets across Computer Vision (CV), Natural Language Processing (NLP), Recommender Systems (RecSys), and Synthetic data demonstrate superior recall and efficiency. Our method achieves up to 35% recall improvement in Recommender Systems, 30.3% in CV, 23.3% in NLP, and 10.1% in Synthetic data, while reducing inference time by 45% (CV), 42% (Synthetic), 20% (NLP), and 25% (Recommender Systems). Ablation studies confirm that LID-based insertion has the most impact, followed by dual-branch search and skip-bridging.
Paper Number
2201
Recommended Citation
Nguyen, Hy; Nguyen, Nguyen Hung; Nguyen, Linh Bao; Thudumu, Srikanth; and Vasa, Rajesh, "HNSW++: A Dual-Branch Hierarchical Navigable Small World Graph with LID-Guided Skip Bridge Optimization" (2025). AMCIS 2025 Proceedings. 47.
https://aisel.aisnet.org/amcis2025/intelfuture/intelfuture/47
HNSW++: A Dual-Branch Hierarchical Navigable Small World Graph with LID-Guided Skip Bridge Optimization
The Hierarchical Navigable Small World (HNSW) algorithm is widely used for approximate nearest neighbor (ANN) search but suffers from local optima, frequently fails to achieve logarithmic complexity and inefficiencies in high-dimensional spaces. We propose a novel algorithm that enhances search accuracy and speed. Our approach introduces a dual-branch HNSW structure with LID-based insertion, improving cluster connectivity and mitigating local minima. Additionally, we incorporate skip-bridge connections, bypassing redundant layers to accelerate inference. Experiments on 12 datasets across Computer Vision (CV), Natural Language Processing (NLP), Recommender Systems (RecSys), and Synthetic data demonstrate superior recall and efficiency. Our method achieves up to 35% recall improvement in Recommender Systems, 30.3% in CV, 23.3% in NLP, and 10.1% in Synthetic data, while reducing inference time by 45% (CV), 42% (Synthetic), 20% (NLP), and 25% (Recommender Systems). Ablation studies confirm that LID-based insertion has the most impact, followed by dual-branch search and skip-bridging.
When commenting on articles, please be friendly, welcoming, respectful and abide by the AIS eLibrary Discussion Thread Code of Conduct posted here.
Comments
IntelFuture