PRO-HNSW: Proactive Repair and Optimization for High-Performance Dynamic HNSW Indexes

Graph-based Approximate Nearest Neighbor Search (ANNS), particularly using Hierarchical Navigable Small World (HNSW) graphs, offers state-of-the-art query performance for large-scale, high-dimensional data. However, the efficiency and accuracy of HNSW indexes degrade seriously under dynamic conditions involving frequent data deletions and reinsertions, often necessitating costly full index rebuilds. This paper introduces PRO-HNSW (Proactive Repair and Optimized HNSW), a novel and lightweight maintenance framework designed to efficiently preserve and even enhance the quality of the HNSW graph in dynamic environments. PRO-HNSW systematically addresses key structural degradation factors by incorporating three targeted modules: (1) a RemoveObsoleteEdges module to prune edges pointing to deleted nodes while preserving minimal connectivity, (2) a RepairDisconnectedNodes module that re-establishes connectivity for isolated nodes via BFS-based neighbor discovery, and (3) a ResolveUnidirectionalEdges module to ensure more balanced and navigable graph structures. Extensive experiments on eight diverse benchmark datasets demonstrate that PRO-HNSW significantly outperforms not only the standard HNSW but also the state-of-the-art MN-RU method. Notably, on the high-dimensional GIST1M dataset under high data churn, PRO-HNSW achieves a peak recall of 84.23%, a significant 2.56 percentage points higher than even the ideal HNSW-Rebuild baseline, showcasing its superior ability to produce a more optimal graph structure. Our findings also reveal that applying specific PRO-HNSW maintenance modules to a freshly built static HNSW index can improve its initial recall, highlighting its utility as a general graph optimization technique. PRO-HNSW thus provides a practical and robust solution for maintaining highperformance ANNS in evolving real-world applications.