I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration

Summary: Introduces an I/O-first framework for SSD-resident graph ANN, modeling how memory/disk layouts and search jointly affect page reads via locality and path length. Systematic composition yields OctopusANN, up to 37.9% faster than Starling and 149.5% faster than DiskANN at Recall@10=90%. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 14481
Venue: VLDB
Year: 2026
Pagerank: 5.093636e-05
Overall Rank: 10,544 | 27.66%
DOI: 10.14778/3801059.3801064

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Liang Li (China Telecom Cloud Computing Research Institute)
2. Shufeng Gong (Northeastern University)
3. Yanan Yang (China Telecom Cloud Computing Research Institute)
4. Yiduo Wang (China Telecom Cloud Computing Research Institute)
5. Jie Wu (China Telecom Cloud Computing Research Institute; Temple University)

BibTeX Citation

@article{li_vldb26,
        title = {{I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration}},
        author = {Li, Liang and Gong, Shufeng and Yang, Yanan and Wang, Yiduo and Wu, Jie},
        journal = {PVLDB},
        series = {{VLDB} '26},
        volume = {19},
        number = {7},
        pages = {1484--1498},
        doi = {10.14778/3801059.3801064},
        url = {https://doi.org/10.14778/3801059.3801064},
        year = {2026}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00034701237
286	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.00022357911
332	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00020920444
398	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00019194947
406	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00019054532
705	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00014829964
926	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.00013181732
1,244	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.00011508159
1,357	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00011043994
1,589	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00010264469
1,735	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	9.9004924e-05
1,760	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	9.8157819e-05
2,010	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.3085202e-05
2,534	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.4561875e-05
3,240	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.6071649e-05
4,712	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.5506649e-05
6,133	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.9654376e-05
7,145	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.6908957e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,886	Approximate NN Queries on Streams with Guaranteed Error/performance Bounds	2004	VLDB
2	1,934	Towards Efficient Index Construction and Approximate Nearest Neighbor Search in High-Dimensional Spaces	2023	VLDB
3	11,751	On the I/O Complexity of the k-Nearest Neighbors Problem	2020	PODS
4	990	SK-LSH: An Efficient Index Structure for Approximate Nearest Neighbor Search	2014	VLDB
5	10,456	FlashANNS: GPU-Driven Asynchronous I/O Pipelining for Eliminating Storage-Compute Bottlenecks in Billion-Scale Similarity Search	2026	SIGMOD
6	7,259	Efficient Dynamic Indexing for Range Filtered Approximate Nearest Neighbor Search	2025	SIGMOD
7	9,778	Turbocharging Vector Databases using Modern SSDs	2025	VLDB
8	93	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB
9	10,227	Efficient Index Layout and Search Strategy for Large-scale High-dimensional Vector Similarity Search	2026	SIGMOD
10	6,615	A Topology-Aware Localized Update Strategy for Graph-Based ANN Index	2026	VLDB