cs.IRJan 5, 2026

MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search

Authors: Dongfang Zhao

Organizations: Tacoma School of Engineering and Technology Paul G. Allen School of Computer Science & Engineering University of Washington

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 allocate the search effort of a graph index according to the intrinsic geometry of data. Specifically, MCGI estimates the LID around each query from the distances that its own search has already computed and resizes the candidate list of the query once, so that queries in high-LID regions receive longer lists while queries in low-LID regions terminate earlier; the estimate itself costs no additional disk reads. Theoretical analysis shows that the success probability of any fixed search list decays exponentially with the LID of the query. At matched high recall, MCGI raises the query throughput of DiskANN on the same standard Vamana index by up to 1.43×1.43\times on three million-scale benchmarks and by up to 1.24×1.24\times on the billion-scale SIFT1B and Deep1B.

Figures & tables

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Approximate Nearest Neighbor Search for Modern AI: A Projection-Augmented Graph Approach

    Mar 1, 2026Kejing Lu, Zhenpeng Pan, Jianbin Qin +2Approximate Nearest Neighbor SearchGraph-Based Retrieval