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× on three million-scale benchmarks and by up to 1.24× on the billion-scale SIFT1B and Deep1B.
Figures & tables
Symbol
Meaning
Source
Typical value
Lˉ
List size that the application requests
Application
–
k
Result size; lower bound of the list size
Application
10
n0
Expansions before the checkpoint
Fixed
24
m
Candidates in the candidate-list LID estimate
Fixed
64
ϵ
Margin of the competition count
Fixed
0.2
f(q)
Five geometric features at the checkpoint
Search
–
Table 1: Quantities of the query-adaptive search list.
Figure 1: Recall-QPS trade-off of MCGI and DiskANN on the million-scale datasets.
Figure 2: Recall-QPS trade-off of MCGI and DiskANN on SIFT1B and Deep1B.
Table 4Figure 5
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
Dataset
N
D
Queries
R
Lbuild
mPQ (Byte)
Data Type
SIFT1M
106
128
10,000
32
50
107
float32
GloVe-100
1.18×106
100
10,000
64
100
90
float32
GIST1M
106
960
1,000
32
100
322
float32
SIFT1B
109
128
5,000
32
50
31
uint8
Deep1B
109
96
4,998
32
50
31
float32
Appendix
Table 4: Dataset specifications and indexing parameters.
Dataset
μLID (Mean)
σLID (Std)
List size Lˉ
γ
Threads
SIFT1M
16.1
9.2
10→400
0.7
32
GloVe-100
35.3
18.1
10→400
1.0
32
GIST1M
48.9
25.9
10→400
0.7
32
SIFT1B
–
–
10→1000
0.7
32
Deep1B
–
–
10→2000
0.7
32
Appendix
Table 5: LID statistics and search parameters.
Figure 5: Recall against the requested list size, and mean latency against recall.
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
Appendix
Table 6: Offline cost in seconds: index build stages and calibration of the query-adaptive search list.
Approximate Nearest Neighbor Search (ANNS) is fundamental to modern AI applications. Most existing solutions optimize query efficiency but fail to align with the practical requirements of modern workloads. In this paper, we outline six critical demands of modern AI applications: high query efficiency, fast indexing, low memory footprint, scalability to high dimensionality, robustness across varying retrieval sizes, and support for online insertions. To satisfy all these demands, we introduce Projection-Augmented Graph (PAG), a new ANNS framework that integrates projection techniques into a graph index. PAG reduces unnecessary exact distance computations through asymmetric comparisons between exact and approximate distances as guided by projection-based statistical tests. Three key components are designed and integrated into the graph index to optimize indexing and searching. Experiments on six modern datasets demonstrate that PAG consistently achieves superior queries per second (QPS)-recall performance -- up to 5x faster than HNSW -- while offering fast indexing speed and moderate memory footprint. PAG remains robust as dimensionality and retrieval size increase and naturally supports online insertions.
Kejing Lu, Zhenpeng Pan, Jianbin Qin +2
University of Yamanashi · Beijing Institute of Technology, Zhuhai · Shenzhen University +2
We present mycelium-index, a streaming approximate nearest neighbor (ANN) index for high-dimensional vector spaces, inspired by the adaptive growth patterns of biological mycelium. The system continuously adapts its topology through myelial edge decay and reinforcement, a traffic-driven living hierarchy, and hybrid deletion combining O(1) bypass for cold nodes with O(k) beam-search repair for hub nodes. Experimental evaluation on SIFT-1M demonstrates that mycelium achieves 0.927 +/- 0.028 recall@5 under FreshDiskANN's 100%-turnover benchmark protocol -- within the measurement confidence interval of FreshDiskANN's ~0.95 -- while using 5.7x less RAM (88 MB vs. >500 MB) and achieving 4.7x higher QPS (2,795 vs. ~600). On the static index, at ef=192, mycelium matches HNSW M=16 recall (0.962 vs. 0.965) at 5.2x less RAM (163 MB vs. 854 MB). Performance optimizations including NEON SIMD distance computation, Vec-backed node storage, and bitset visited tracking yield a cumulative 2.7x QPS improvement. A systematic study of ten streaming repair mechanisms finds that geometric heuristics universally fail in high dimensions, while topological mechanisms succeed -- a principle we term the topological repair invariance of high-dimensional ANN graphs.
The most popular graph indices for vector search use principles from computational geometry to build the graph. Hence, their formal graph navigability guarantees are only valid in Euclidean space. In this work, we show that machine learning can be used to build graph indices for vector search in metric and non-metric vector spaces (e.g., for inner product similarity). From this novel perspective, we introduce the Support Vector Graph (SVG), a new type of graph index that leverages kernel methods to establish the graph connectivity and that comes with formal navigability guarantees valid in metric and non-metric vector spaces. In addition, we interpret the most popular graph indices, including HNSW and DiskANN, as particular specializations of SVG and show that new navigable indices can be derived from the principles behind this specialization. Finally, we propose SVG-L0 that incorporates an ℓ0 sparsity constraint into the SVG kernel method to build graphs with a bounded out-degree. This yields a principled way of implementing this practical requirement, in contrast to the traditional heuristic of simply truncating the out edges of each node. Additionally, we show that SVG-L0 has a self-tuning property that avoids the heuristic of using a set of candidates to find the out-edges of each node and that keeps its computational complexity in check.