I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration
Proceedings of the VLDB Endowment · 01.03.2026 · 19 (7) · 1484-1498
DOI: 10.14778/3801059.3801064 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the VLDB Endowment, online erschienen am 14.07.2026. Verfasst von Liang Li und 4 weiteren Autor:innen. Die Arbeit wurde bisher 2-mal zitiert (Crossref) und nennt 100 Literaturangaben.
Abstract (Originalsprache)
Approximate nearest neighbor (ANN) search on SSD-backed indexes is increasingly I/O-bound (I/O accounts for 70–90% of query latency). We present an I/O-first framework for disk-based ANN that organizes techniques along three dimensions: memory layout, disk layout, and search algorithm. We introduce a page-level complexity model that explains how page locality and path length jointly determine page reads, and we validate the model empirically. Using consistent implementations across four public datasets, we quantify both single-factor effects and cross-dimensional synergies. We find that (i) memory-resident navigation and dynamic width provide the strongest standalone gains; (ii) page shuffle and page search are weak alone but complementary together; and (iii) a principled composition, OctopusANN, substantially reduces I/O and achieves 4.1–37.9% higher throughput than the state-of-the-art system Starling and 87.5–149.5% higher throughput than DiskANN at matched Recall@10=90%. Finally, we distill actionable guidelines for selecting storage-centric or hybrid designs across diverse concurrency levels and accuracy constraints, advocating systematic composition rather than isolated tweaks when pushing the performance frontier of disk-based ANN.
Zitieren
APA
Li, L., Gong, S., Yang, Y., Wang, Y., & Wu, J. (2026). I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration. Proceedings of the VLDB Endowment, 19(7), 1484-1498. https://doi.org/10.14778/3801059.3801064
Vancouver
Li L, Gong S, Yang Y, Wang Y, Wu J. I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration. Proceedings of the VLDB Endowment. 2026;19(7):1484-1498. doi:10.14778/3801059.3801064
BibTeX
@article{Li2026,
author = {Li, Liang and Gong, Shufeng and Yang, Yanan and Wang, Yiduo and Wu, Jie},
title = {I/O Optimizations for Graph-Based Disk-Resident Approximate Nearest Neighbor Search: A Design Space Exploration},
journal = {Proceedings of the VLDB Endowment},
year = {2026},
volume = {19},
number = {7},
pages = {1484--1498},
doi = {10.14778/3801059.3801064}
}
EUVIMED