arXiv:2510.25401cs.DBcs.IR2025-10被引 4

分离向量与图结构,实现高效更新与低延迟查询。

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

  • 解耦存储:向量与图拓扑物理分离,减少更新时冗余读写。
  • 更新提速8.17倍,混合负载下查询延迟降低67%。
  • 适合需要频繁更新的海量向量检索场景。

基于磁盘的图索引因其高性能和高性价比,被广泛用于十亿级近似最近邻搜索(ANNS)。然而,现有系统通常采用耦合存储架构,将向量与图拓扑共同存放,导致更新时产生大量冗余I/O,影响动态工作负载下的可用性。本文提出一种解耦存储架构,将重型向量与轻量级图拓扑物理分离,显著提升更新性能。但该设计带来查询时的I/O放大问题。为改善在更新友好架构下的查询效率,我们提出两项协同设计技术:一是相似性感知的动态布局,在线优化数据放置,使重复读取的数据可在后续搜索步骤中复用,将读放大转化为有效预取;二是两级查询机制,结合分层乘积量化(hierarchical PQ),快速准确筛选候选集,并仅对少量候选进行原始向量精炼,大幅降低精炼阶段的I/O与计算开销。实验表明,DGAI在插入与删除操作上分别提升8.17倍和8.16倍更新速度,混合工作负载下峰值查询延迟降低67%,实现了资源高效更新与低延迟查询的兼顾。

原文摘要 · Abstract (English)

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 efficiency.To 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.

近似搜索图索引更新高效磁盘存储

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。