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

• URL: http://arxiv.org/abs/2601.01930v1
• Date: Mon, 05 Jan 2026 09:23:48 GMT
• Title: MCGI: Manifold-Consistent Graph Indexing for Billion-Scale Disk-Resident Vector Search
• Abstract summary: MCGI is a geometry-aware and disk-resident indexing method that adapts search strategies to the data's intrinsic geometry.<n> Empirically, MCGI achieves 5.8$times$ higher throughput at 95% recall on high-dimensional GIST1M compared to state-of-the-art DiskANN.<n>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.
• Score: 0.9179857807576733
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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, 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.

Related papers

• LLM-Aided A* Search in Non-Geometric Network Graphs [0.4078247440919473]
  We propose a large language model (LLM)-aided A* algorithm in which an LLM generates intermediate waypoints that guide the A* expansion toward promising graph regions.<n>Our experiments on multiple graph topologies with up to 2,000 nodes demonstrate that LLM reduce the number of expanded nodes by around 50% while incurring only a marginal path cost increase compared to the optimal solution.
  arXiv  Detail & Related papers  (2026-06-22T10:26:35Z)
• Edge-directed geometric partitioning for versatile video coding [57.010424923769385]
  We propose a GEO mode prediction strategy by constructing a Most Probable Mode (MPM) list to reduce the overhead of GEO and improve coding efficiency.<n>The proposed method provides an objective BD-rate gain of 0.58% and 1.00% on average for RA LDB configurations compared to VTM-6.0.
  arXiv  Detail & Related papers  (2026-06-01T03:47:14Z)
• A Mean Curvature Approach to Boundary Detection: Geometric Insights for Unsupervised Learning [52.452902154360565]
  We introduce Mean Curvature Boundary Points (MCBP), a novel geometric framework grounded in Geometric Machine Learning.<n>MCBP explicitly models the intrinsic curvature of the data manifold and computes pointwise mean curvature without requiring principled manifold parametrization.<n>Experiments on synthetic and real-world datasets demonstrate that MCBP consistently improves clustering performance.
  arXiv  Detail & Related papers  (2026-05-05T20:19:09Z)
• Differentiable Geometric Indexing for End-to-End Generative Retrieval [32.54110566819413]
  Generative Retrieval (GR) has emerged as a promising paradigm to unify indexing and search within a single probabilistic framework.<n>Existing approaches suffer from two intrinsic conflicts.<n>We propose Differentiable Geometric Indexing (DGI) to resolve these misalignments.
  arXiv  Detail & Related papers  (2026-03-11T04:46:42Z)
• Understanding and Improving UMAP with Geometric and Topological Priors: The JORC-UMAP Algorithm [1.7484982792736636]
  dimensionality reduction techniques, particularly UMAP, are widely used for visualizing high-dimensional data.<n>We introduce Ollivier-Ricci curvature as a geometric prior, reinforcing edges at geometric bottlenecks and reducing redundant links.<n>Experiments on synthetic and real-world datasets show that JORC-UMAP reduces tearing and collapse more effectively than standard UMAP and other DR methods.
  arXiv  Detail & Related papers  (2026-01-23T08:42:56Z)
• GeoRA: Geometry-Aware Low-Rank Adaptation for RLVR [10.820638016337869]
  We propose GeoRA, which exploits the anisotropic and compressible nature of RL update subspaces.<n>GeoRA mitigates optimization bottlenecks caused by geometric misalignment.<n>It consistently outperforms established low-rank baselines on key mathematical benchmarks.
  arXiv  Detail & Related papers  (2026-01-14T10:41:34Z)
• Lighter-X: An Efficient and Plug-and-play Strategy for Graph-based Recommendation through Decoupled Propagation [49.865020394064096]
  We propose textbfLighter-X, an efficient and modular framework that can be seamlessly integrated with existing GNN-based recommender architectures.<n>Our approach substantially reduces both parameter size and computational complexity while preserving the theoretical guarantees and empirical performance of the base models.<n>Experiments demonstrate that Lighter-X achieves comparable performance to baseline models with significantly fewer parameters.
  arXiv  Detail & Related papers  (2025-10-11T08:33:08Z)
• Empowering Graph-based Approximate Nearest Neighbor Search with Adaptive Awareness Capabilities [19.352675865525395]
  This paper proposes GATE, high-tier proximity Graph with Adaptive Topology and Query AwarEness.<n>Gate achieves a 1.2-2.0X speed-up in query performance compared to state-of-the-art graph-based indexes.
  arXiv  Detail & Related papers  (2025-06-19T03:07:12Z)
• Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics [59.07903030446756]
  Graph neural networks are highly vulnerable to distribution shifts on graphs.<n>We present Gadget, the first framework for non-IID graph data.<n> Gadget can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs.
  arXiv  Detail & Related papers  (2025-05-19T05:03:58Z)
• Stitching Inner Product and Euclidean Metrics for Topology-aware Maximum Inner Product Search [21.295432955733197]
  We introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS)<n>Building on these insights, we introduce a novel graph-based index called Metric-Amphibious Graph (MAG) and a corresponding search algorithm, Adaptive Navigation with Metric Switch (ANMS)
  arXiv  Detail & Related papers  (2025-04-21T05:01:58Z)
• A Mapper Algorithm with implicit intervals and its optimization [0.3683202928838613]
  The Mapper algorithm is an essential tool for visualizing complex, high dimensional data in topology data analysis.<n>The need for manual parameter tuning and fixed intervals, along with fixed overlapping ratios may impede the performance of the standard Mapper algorithm.<n>We introduce a novel framework that implicitly represents intervals through a hidden assignment matrix.
  arXiv  Detail & Related papers  (2024-12-16T10:16:54Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching. Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
  arXiv  Detail & Related papers  (2022-10-14T01:42:05Z)
• ZARTS: On Zero-order Optimization for Neural Architecture Search [94.41017048659664]
  Differentiable architecture search (DARTS) has been a popular one-shot paradigm for NAS due to its high efficiency. This work turns to zero-order optimization and proposes a novel NAS scheme, called ZARTS, to search without enforcing the above approximation. In particular, results on 12 benchmarks verify the outstanding robustness of ZARTS, where the performance of DARTS collapses due to its known instability issue.
  arXiv  Detail & Related papers  (2021-10-10T09:35:15Z)
• Robust Training in High Dimensions via Block Coordinate Geometric Median Descent [69.47594803719333]
  Geometric median (textGm) is a classical method in statistics for achieving a robust estimation of the uncorrupted data. In this paper, we show that by that by applying textscGm to only a chosen block of coordinates at a time, one can retain a breakdown point of 0.5 judiciously for smooth nontext problems.
  arXiv  Detail & Related papers  (2021-06-16T15:55:50Z)
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image [88.60285937702304]
  This paper proposes a novel unsupervised approach called spatial-spectral clustering with anchor graph (SSCAG) for HSI data clustering. The proposed SSCAG is competitive against the state-of-the-art approaches.
  arXiv  Detail & Related papers  (2021-04-24T08:09:27Z)
• Mix Dimension in Poincar\'{e} Geometry for 3D Skeleton-based Action Recognition [57.98278794950759]
  Graph Convolutional Networks (GCNs) have already demonstrated their powerful ability to model the irregular data. We present a novel spatial-temporal GCN architecture which is defined via the Poincar'e geometry. We evaluate our method on two current largest scale 3D datasets.
  arXiv  Detail & Related papers  (2020-07-30T18:23:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.