解决万亿级向量搜索索引构建慢的问题，提升工业级可扩展性。
Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search
- 动态分块并允许子集重叠，缓解数据过载问题。
- 分布式构建子图，平均构建时间减少47.3%。
- 已落地真实搜索引擎，支撑百亿级每日更新向量。
近似最近邻搜索（ANNS）是现代数据驱动应用中从海量向量数据库高效检索前k个结果的关键技术。尽管现有基于图的ANNS算法在十亿级数据集上能实现高召回率，但其构建速度慢、可扩展性差，限制了在大规模工业场景中的应用。本文提出SOAGIC——首个面向超大规模向量数据库的可扩展、负载感知的图结构索引构建系统：1）设计一种带负载约束的动态数据分块算法，自适应引入子集重叠；2）通过负载均衡任务调度框架与凝聚式合并策略，实现高效的分布式子图构建；3）在多个数据集上的实验表明，相比现有方法，平均构建时间降低47.3%。该方法已在真实工业搜索引擎中成功部署，管理超过100亿条每日更新的向量，服务数亿用户。
原文摘要 · Abstract (English)
Approximate Nearest Neighbor Search (ANNS) is essential for modern data-driven applications that require efficient retrieval of top-k results from massive vector databases. Although existing graph-based ANNS algorithms achieve a high recall rate on billion-scale datasets, their slow construction speed and limited scalability hinder their applicability to large-scale industrial scenarios. In this paper, we introduce SOGAIC, the first Scalable Overload-Aware Graph-Based ANNS Index Construction system tailored for ultra-large-scale vector databases: 1) We propose a dynamic data partitioning algorithm with overload constraints that adaptively introduces overlaps among subsets; 2) To enable efficient distributed subgraph construction, we employ a load-balancing task scheduling framework combined with an agglomerative merging strategy; 3) Extensive experiments on various datasets demonstrate a reduction of 47.3% in average construction time compared to existing methods. The proposed method has also been successfully deployed in a real-world industrial search engine, managing over 10 billion daily updated vectors and serving hundreds of millions of users.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。