DGAI: Decoupled On-Disk Graph-Based ANN Index for Efficient Updates and Queries

View PDF HTML (experimental)

Abstract:On-disk graph-based indexes are favored for billion-scale Approximate Nearest Neighbor Search (ANNS) due to their high performance and cost-efficiency. However, existing systems typically rely on a coupled storage architecture that co-locates vectors and graph topology, which introduces substantial redundant I/O during index updates, thereby degrading usability in dynamic workloads. In this paper, we propose a decoupled storage architecture that physically separates heavy vectors from the lightweight graph topology. This design substantially improves update performance by reducing redundant I/O during updates. However, it introduces I/O amplification during ANNS, leading to degraded query this http URL improve query performance within the update-friendly architecture, we propose two techniques co-designed with the decoupled storage. We develop a similarity-aware dynamic layout that optimizes data placement online so that redundantly fetched data can be reused in subsequent search steps, effectively turning read amplification into useful prefetching. In addition, we propose a two-stage query mechanism enhanced by hierarchical PQ, which uses hierarchical PQ to rapidly and accurately identify promising candidates and performs exact refinement on raw vectors for only a small number of candidates. This design significantly reduces both the I/O and computational cost of the refinement stage. Overall, DGAI achieves resource-efficient updates and low-latency queries simultaneously. Experimental results demonstrate that \oursys improves update speed by 8.17x for insertions and 8.16x for deletions, while reducing peak query latency under mixed workloads by 67% compared to state-of-the-art baselines.

Comments: 12 pages

Subjects:

Databases (cs.DB); Information Retrieval (cs.IR)

Cite as: arXiv:2510.25401 [cs.DB]

(or arXiv:2510.25401v3 [cs.DB] for this version)

https://doi.org/10.48550/arXiv.2510.25401

arXiv-issued DOI via DataCite

Submission history

From: Tom. Lou [view email] [v1] Wed, 29 Oct 2025 11:20:10 UTC (1,139 KB) [v2] Thu, 11 Dec 2025 21:14:45 UTC (196 KB) [v3] Thu, 2 Apr 2026 15:41:26 UTC (1,218 KB)