View PDF HTML (experimental)

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 OrchANN (Orchestrated ANN Search), an out-of-core ANNS engine that orchestrates query routing, partition access, and query execution under tight memory constraints. OrchANN 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, OrchANN 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, OrchANN delivers up to 17.2x higher QPS and 25.0x lower latency than state-of-the-art baselines, while preserving accuracy.

Submission history

From: Lizheng Chen [view email]
[v1] Sun, 28 Dec 2025 08:42:38 UTC (624 KB)
[v2] Tue, 7 Jul 2026 09:01:40 UTC (2,056 KB)