BAMG: A Block-aware Monotonic Graph Index For Disk-based Approximate Nearest Neighbor Search
2025 · Huiling Li, Xin Huang, Byron Choi, et al.
Abstract
Approximate Nearest Neighbor Search (ANNS) over high-dimensional vectors is a foundational problem in databases, where disk I/O often emerges as the dominant performance bottleneck at scale. To accelerate search, graph-based indexes rely on proximity graph, where nodes represent vectors and edges guide the traversal toward the target. However, existing graph indexing solutions for disk-based ANNS typically either optimize the storage layout for a given graph or construct the graph independently of the storage layout, thus overlooking their interaction. In this paper, we bridge this gap by proposing the Block-aware Monotonic Relative Neighborhood Graph (BMRNG), theoretically guaranteeing the existence of I/O monotonic search paths. The core idea is to align the graph topology with the data placement by jointly considering both geometric distance and storage layout for edge selection. To address the scalability challenge of BMRNG construction, we further develop a practical and efficient
Authors
(none)
Tags
Stats
Related papers
- DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
- Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph (2017)18.20
- MCGI: Manifold-consistent Graph Indexing For Billion-scale Disk-resident Vector Search (2026)0.00
- Diskann++: Efficient Page-based Search Over Isomorphic Mapped Graph Index Using Query-sensitivity Entry Vertex (2023)0.00
- Freshdiskann: A Fast And Accurate Graph-based ANN Index For Streaming Similarity Search (2021)0.00
- Understanding And Generalizing Monotonic Proximity Graphs For Approximate Nearest Neighbor Search (2021)0.00
- In-place Updates Of A Graph Index For Streaming Approximate Nearest Neighbor Search (2025)0.00
- Theoretical And Empirical Analysis Of Adaptive Entry Point Selection For Graph-based Approximate Nearest Neighbor Search (2024)0.00