Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search

Abstract

Proximity graphs (PG) have gained increasing popularity as the state-of-the-art solutions to \(k\)-approximate nearest neighbor (\(k\)-ANN) search on high-dimensional data, which serves as a fundamental function in various fields, e.g., retrieval-augmented generation. Although PG-based approaches have the best \(k\)-ANN search performance, their index construction cost is superlinear to the number of points. Such superlinear cost substantially limits their scalability in the era of big data. Hence, the goal of this paper is to accelerate the construction of PG-based methods without compromising their \(k\)-ANN search performance. To achieve this goal, two mainstream categories of PG are revisited: relative neighborhood graph (RNG) and navigable small world graph (NSWG). By revisiting their construction process, we find the issues of construction efficiency. To address these issues, we propose a new construction framework with a novel pruning strategy for edge selection, which acceler

Stats

• citations8
• S2 citations—
• github stars0
• HF likes0
• heat score7.16
• arxiv keyyang2024revisiting

Related papers

• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• Revisiting \(k\)-nearest Neighbor Graph Construction On High-dimensional Data : Experiments And Analyses (2021)0.00
• Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00
• Relative Nn-descent: A Fast Index Construction For Graph-based Approximate Nearest Neighbor Search (2023)8.09
• Pgtuner: An Efficient Framework For Automatic And Transferable Configuration Tuning Of Proximity Graphs (2025)1.69
• Sparse Neighborhood Graph-based Approximate Nearest Neighbor Search Revisited: Theoretical Analysis And Optimization (2025)0.00
• A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph (2023)0.00
• Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20