Beyond Overlap: Hierarchical Graph Abstraction for Out-of-Core Vector Search
Lizheng Chen, Pinhuan Wang, Shaonan Ma*, Jie Zhang, Qing Wang, Zhengyi Yang, Heng Zhang, Mingxing Zhang, Fan Yang, Guihai Chen, Chen Tian, Chengying Huan
RAIDS Lab Authors
Details
Research Area
Tags
Abstract
At billion scale, approximate nearest neighbor search (ANNS) often becomes an out-of-core problem: the full vector collection and index structures exceed memory capacity, making query performance dominated by SSD accesses and DRAM-SSD data movement. Existing systems struggle to strike a balance between accuracy and efficiency: physical-overlap methods replicate vectors or index entries across partitions, enlarging the SSD-resident index and incurring extra I/O; quantization-based methods reduce memory usage, but their approximate distances are less reliable and often require costly raw-vector reranking from SSD to preserve recall. We present GANNS (Graph-Abstraction ANNS), a hierarchical out-of-core ANNS engine that improves accuracy and I/O efficiency simultaneously. GANNS stores each cluster as a disjoint SSD partition with scale-aware indexes, while a memory-resident graph abstraction provides logical overlap before SSD access. During serving, GANNS uses query hotness and cluster priorities from the graph abstraction to prune low-value clusters and improve access locality. Across five datasets under strict memory constraints, GANNS delivers up to 17.2x higher QPS and 25.0x lower latency than state-of-the-art baselines, while preserving accuracy.