Enhancing HNSW Index For Real-time Updates: Addressing Unreachable Points And Performance Degradation

Abstract

The approximate nearest neighbor search (ANNS) is a fundamental and essential component in data mining and information retrieval, with graph-based methodologies demonstrating superior performance compared to alternative approaches. Extensive research efforts have been dedicated to improving search efficiency by developing various graph-based indices, such as HNSW (Hierarchical Navigable Small World). However, the performance of HNSW and most graph-based indices become unacceptable when faced with a large number of real-time deletions, insertions, and updates. Furthermore, during update operations, HNSW can result in some data points becoming unreachable, a situation we refer to as the `unreachable points phenomenon'. This phenomenon could significantly affect the search accuracy of the graph in certain situations. To address these issues, we present efficient measures to overcome the shortcomings of HNSW, specifically addressing poor performance over long periods of delete and update

Stats

• citations0
• S2 citations—
• github stars5
• HF likes0
• heat score1.56
• arxiv keyxiao2024enhancing

Related papers

• In-place Updates Of A Graph Index For Streaming Approximate Nearest Neighbor Search (2025)0.00
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
• Frequency-aware Graph Construction And Search For Dynamic Vector Databases (2025)0.00
• Freshdiskann: A Fast And Accurate Graph-based ANN Index For Streaming Similarity Search (2021)0.00
• DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
• Efficient And Robust Approximate Nearest Neighbor Search Using Hierarchical Navigable Small World Graphs (2016)22.99
• Down With The Hierarchy: The 'H' In HNSW Stands For "hubs" (2024)0.00
• A Revisit Of Hashing Algorithms For Approximate Nearest Neighbor Search (2016)11.19