MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search
This addresses the challenge of efficient billion-scale vector search for applications like image retrieval, though it is incremental as it builds on existing graph-based ANN methods.
The paper tackled the problem of performance degradation in graph-based approximate nearest neighbor search in high-dimensional spaces due to the Euclidean-Geodesic mismatch, and proposed MCGI, which achieved 5.8x higher throughput at 95% recall on GIST1M and 3x reduced query latency on SIFT1B compared to state-of-the-art methods.
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, we propose 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 data's intrinsic geometry. Unlike standard algorithms that treat dimensions uniformly, MCGI modulates its beam search budget based on in situ geometric analysis, eliminating dependency on static hyperparameters. Theoretical analysis confirms that MCGI enables improved approximation guarantees by preserving manifold-consistent topological connectivity. Empirically, MCGI achieves 5.8$\times$ higher throughput at 95\% recall on high-dimensional GIST1M compared to state-of-the-art DiskANN. On the billion-scale SIFT1B dataset, MCGI further validates its scalability by reducing high-recall query latency by 3$\times$, while maintaining performance parity on standard lower-dimensional datasets.