Optimized Framework for Merging Navigable Small-World Graphs: Balancing Efficiency and Search Performance

Navigable small-world graphs have emerged as fundamental structures for efficient a pproximate n earest neighbour (ANN) search in high-dimensional spaces, with applications spanning recommendation systems, image retrieval, and natural language processing. However, the challenge of merging such graphs while preserving their navigability and search efficiency$r$emains$l$argely$u$naddressed.$T$his$p$aper introduces a novel optimisation framework for merging navigable smallworld graphs that strategically balances computational efficiency with search performance. We propose three progressive merging algorithms-Naive Merge, Merge1, and Merge2-that employ localised proximity-based neighbourhood construction and adaptive exploration-exploitation strategies to minimise redundancy and ensure seamless graph integration. Comprehensive experimental evaluation on the Sift1M dataset demonstrates that our advanced merging algorithms reduce computational effort by up to 5x compared to baseline approaches while maintaining competitive search accuracy. The proposed framework provides a scalable solution for dynamic and distributed graph-based systems requiring efficient index maintenance and consolidation.