MCGI: Manifold-consistent Graph Indexing For Billion-scale Disk-resident Vector Search
2026 · Dongfang Zhao
Abstract
arXiv:2601.01930v3 Announce Type: replace Abstract: Graph-based Approximate Nearest Neighbor (ANN) search often suffers from performance degradation in high-dimensional spaces due to the Euclidean-Geodesic mismatch, where greedy routing diverges from the underlying data manifold. To address this challenge, this paper presents Manifold-Consistent Graph Indexing (MCGI), a geometry-aware and disk-resident indexing method that leverages Local Intrinsic Dimensionality (LID) to dynamically adapt search strategies to the intrinsic geometry of data. Unlike conventional algorithms that treat dimensions uniformly, MCGI modulates its beam search budget based on in-situ geometric analysis, which reduces sensitivity to data-specific hyperparameters by replacing a single scalar with a geometry-informed range that remains stable across datasets of varying dimensionality. Theoretical analysis demonstrates that MCGI provides robust approximation by preserving manifold-consistent topological connectivi
Authors
(none)
Tags
Stats
Related papers
- DGAI: Decoupled On-disk Graph-based ANN Index For Efficient Updates And Queries (2025)0.00
- BAMG: A Block-aware Monotonic Graph Index For Disk-based Approximate Nearest Neighbor Search (2025)0.00
- Diskann++: Efficient Page-based Search Over Isomorphic Mapped Graph Index Using Query-sensitivity Entry Vertex (2023)0.00
- Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
- High Dimensional Similarity Search With Satellite System Graph: Efficiency, Scalability, And Unindexed Query Compatibility (2019)17.30
- Scalable Overload-aware Graph-based Index Construction For 10-billion-scale Vector Similarity Search (2025)4.52
- Revisiting The Index Construction Of Proximity Graph-based Approximate Nearest Neighbor Search (2024)7.16
- Freshdiskann: A Fast And Accurate Graph-based ANN Index For Streaming Similarity Search (2021)0.00