MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search
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 on three million-scale benchmarks and by up to on the billion-scale SIFT1B and Deep1B.
Figures & tables
| Symbol | Meaning | Source | Typical value |
|---|---|---|---|
| List size that the application requests | Application | – | |
| Result size; lower bound of the list size | Application | 10 | |
| Expansions before the checkpoint | Fixed | 24 | |
| Candidates in the candidate-list LID estimate | Fixed | 64 | |
| Margin of the competition count | Fixed | 0.2 | |
| Five geometric features at the checkpoint | Search | – |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Dataset | Queries | (Byte) | Data Type | ||||
|---|---|---|---|---|---|---|---|
| SIFT1M | 128 | 10,000 | 32 | 50 | 107 | float32 | |
| GloVe-100 | 100 | 10,000 | 64 | 100 | 90 | float32 | |
| GIST1M | 960 | 1,000 | 32 | 100 | 322 | float32 | |
| SIFT1B | 128 | 5,000 | 32 | 50 | 31 | uint8 | |
| Deep1B | 96 | 4,998 | 32 | 50 | 31 | float32 |
| Dataset | (Mean) | (Std) | List size | Threads | |
|---|---|---|---|---|---|
| SIFT1M | 16.1 | 9.2 | 0.7 | 32 | |
| GloVe-100 | 35.3 | 18.1 | 1.0 | 32 | |
| GIST1M | 48.9 | 25.9 | 0.7 | 32 | |
| SIFT1B | – | – | 0.7 | 32 | |
| Deep1B | – | – | 0.7 | 32 |
| Dataset | PQ training | Graph | Disk layout | Total build | Calibration |
|---|---|---|---|---|---|
| SIFT1M | 195 | 6 | 1 | 203 | 174 |
| GloVe-100 | 400 | 15 | 1 | 416 | 168 |
| GIST1M | 1,678 | 82 | 4 | 1,764 | 174 |
| SIFT1B | 2,775 | 14,117 | 290 | 17,225 | 94 |
| Deep1B | 3,373 | 15,029 | 836 | 19,317 | 289 |
Approximate Nearest Neighbor Search
Approximate nearest neighbor search finds close vectors without exhaustive comparisons, enabling scalable retrieval in high-dimensional datasets.
See all 48 papers