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: h82420f6da224a8ce
Venue: VLDB
Year: 2026
Pagerank: 4.9769913e-05
Overall Rank: 10,736 | 27.85%
DOI: 10.14778/3801059.3801064
PDF: Download (CC BY-NC-ND 4.0)

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
74	Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph	2019	VLDB	0.00037145866
189	Milvus: A Purpose-Built Vector Data Management System	2021	SIGMOD	0.0002585319
297	Query-Aware Locality-Sensitive Hashing for Approximate Nearest Neighbor Search	2016	VLDB	0.00021849337
339	AnalyticDB-V: A Hybrid Analytical Engine Towards Query Fusion for Structured and Unstructured Data	2020	VLDB	0.00020561716
344	A Comprehensive Survey and Experimental Comparison of Graph-Based Approximate Nearest Neighbor Search	2021	VLDB	0.00020455839
648	HD-Index: Pushing the Scalability-Accuracy Boundary for Approximate kNN Search in High-Dimensional Spaces	2018	VLDB	0.00015156941
803	RaBitQ: Quantizing High-Dimensional Vectors with a Theoretical Error Bound for Approximate Nearest Neighbor Search	2024	SIGMOD	0.00013838349
838	Improving Approximate Nearest Neighbor Search through Learned Adaptive Early Termination	2020	SIGMOD	0.0001355054
1,166	Efficient Approximate Nearest Neighbor Search in Multi-dimensional Databases	2023	SIGMOD	0.0001172922
1,456	Manu: A Cloud Native Vector Database Management System	2022	VLDB	0.00010588868
1,600	High-Dimensional Approximate Nearest Neighbor Search: with Reliable and Efficient Distance Comparison Operations	2023	SIGMOD	0.00010111099
1,603	Starling: An I/O-Efficient Disk-Resident Graph Index Framework for High-Dimensional Vector Similarity Search on Data Segment	2024	SIGMOD	0.00010100279
1,894	iDEC: Indexable Distance Estimating Codes for Approximate Nearest Neighbor Search	2020	VLDB	9.4129766e-05
2,264	ELPIS: Graph-Based Similarity Search for Scalable Data Science	2023	VLDB	8.7286407e-05
2,872	Graph-Based Vector Search: An Experimental Evaluation of the State-of-the-Art	2025	SIGMOD	7.9191725e-05
4,051	Revisiting the Index Construction of Proximity Graph-Based Approximate Nearest Neighbor Search	2025	VLDB	6.8266649e-05
6,244	Efficient Data-aware Distance Comparison Operations for High-Dimensional Approximate Nearest Neighbor Search	2025	VLDB	5.8355024e-05
7,267	Subspace Collision: An Efficient and Accurate Framework for High-dimensional Approximate Nearest Neighbor Search	2025	SIGMOD	5.5677188e-05

Semantically Similar Papers

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