DAPG: Distance-Aware Pruning for Dynamic Graph-Based Approximate Nearest Neighbor Search

Approximate nearest neighbor (ANN) search over high-dimensional vector data is a core component of vector databases, recommendation systems, and retrieval-augmented generation. Graph-based indexes provide strong search efficiency, but most are designed for largely static datasets. This implies that under frequent insertions and deletions: (i) graph connectivity may degrade, (ii) maintenance cost can increase, and (iii) redundant edges can further increase query latency and memory usage. To address these challenges, we propose the Distance-Aware Pruned Graph (DAPG), a dynamic graph-based ANN index designed to maintain high-recall search while supporting efficient updates. DAPG constructs an LSH-seeded single-layer proximity graph and applies a two-stage pruning strategy that balances sparsity and navigability. First, a node-specific percentile threshold adapts edge retention to the local distance distribution. Second, adaptive global sparsification constrains high-degree nodes and removes redundant connectivity. For dynamic workloads, DAPG performs localized maintenance by reapplying pruning only to affected hash buckets, candidate neighborhoods, and adjacency lists, thereby avoiding full index reconstruction. We implement DAPG and evaluate it on seven datasets against eleven representative ANN baselines, including state-of-the-art dynamic methods. In static search, DAPG improves the recall-latency trade-off, reducing query latency by up to $65.6\%$. For dynamic workloads, DAPG reduces maintenance time by up to $715\times$ relative to rebuild-based baselines. On MS-MARCO1M, specifically, DAPG achieves average Recall@100 of $0.9680$ compared to $0.9485$ for Wolverine++, while providing $11.0\times$ higher deletion throughput.