Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search Conference: Companion Proceedings of the ACM Web Conference 2025; April 28-May 2, 2025; Sydney, NSW, Australia Companion Proceedings of the ACM Web Conference 2025 (WWW Companion ’25), April 28-May 2

Yang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao Hu · 2025

Read Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search Conference: Companion Proceedings of the ACM Web Conference 2025; April 28-May 2, 2025; Sydney, NSW, Australia Companion Proceedings of the ACM Web Conference 2025 (WWW Companion ’25), April 28-May 2 by Yang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao Hu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-20695.txt.

Introduction

Yang Shi and co-authors build a search index for ten billion vectors without tipping the load. Their twenty twenty-five paper tackles nearest neighbor search, the retrieval core of image, text, and product engines. Graph indexes recall well at billion scale but build slowly and unevenly.

Their system splits data with overlap caps so no shard swells past its share. A scheduler balances the build across machines, and finished parts merge in stages. Tests across datasets show the build holds up at extreme scale. Every AI product that searches embeddings rides on such indexes; faster, steadier builds mean fresher search over collections that never stop growing.

Catalog record

CREATORYang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao Hu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE20 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-20695

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Scalable Overload-Aware Graph-Based Index Construction for 10-Billion-Scale Vector Similarity Search Conference: Companion Proceedings of the ACM Web Conference 2025; April 28-May 2, 2025; Sydney, NSW, Australia Companion Proceedings of the ACM Web Conference 2025 (WWW Companion ’25), April 28-May 2, 2025, Sydney, NSW, Australia DOI: 10.1145/3701716.3715576 ISBN: 979-8-4007-1331-6/2025/04 CCS: Information systems Search engine indexing CCS: Information systems Web search engines CCS: Information systems Database management system engines CCS: Computing methodologies Distributed computing methodologies Yang Shi, Yiping Sun, Jiaolong Du, Xiaocheng Zhong, Zhiyong Wang, Yao Hu Abstract . 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 S calable O verload-Aware G raph-Based A NNS I ndex C onstruction 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 % 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. 1. Introduction Approximate Nearest Neighbor Search (ANNS) has been extensively studied in many recent research ( Ootomo et al. 2024 ; Sun et al. 2024 ; Khan et al. 2024 ) due to its crucial role in a wide range of applications, such as web search engines, recommendation systems, and Retrieval-Augmented Generation (RAG) ( Jiang et al. 2024 ) for large language models (LLMs). These applications rely heavily on ANNS for efficient retrieval of top-k results. Among all ANNS algorithms, graph-based ones ( Wang et al. 2021 ) such as HNSW ( Malkov and Yashunin 2018 ) , NSG ( Fu et al. 2017 ) , and NGT ( Iwasaki and Miyazaki 2018 ) have emerged as highly effective paradigms due to their ability to represent neighbor relationships in a graph structure, which significantly reduces the computational burden required for high-quality retrieval, especially comparing to space-partitioning methods such as IVF, KD-tree ( Ram and Sinha 2019 ) , and LSH ( Huang et al. 2015 ) . Recently, approaches like DiskANN ( Jayaram Subramanya et al. 2019 ) have been developed to construct SSD-resident ANNS graph indexes for billion-scale search, minimizing disk I/O while using limited main memory. However, their index construction process, based on divide-and-conquer ( Bentley 1980 ) , is slow and hard to scale, hindering daily or more frequent updates of vector embeddings in real-world applications. The difficulty arises from two key challenges: Firstly, efficiently creating overlapped subset divisions for large datasets with overload-aware considerations remains unexplored. DiskANN introduces overlap among subsets by assigning each vector to a fixed number of subsets based on its distance to centroids from clustering. However, this approach often results in redundant overlap between geometrically close divisions and sometimes fails to ensure balanced vector assignments due to the uneven distribution of points in the clusters, a consequence of K-means clustering with limited samples. This imbalance can cause a subset’s subgraph construction to exceed resource limits, also known as overload issues, influencing the overall process. While density-based methods like DBSCAN offer more precise divisions, they are impractical for large datasets due to high computational costs, parameter sensitivity, and centroid control challenges. Thus, a more adaptive data partitioning approach is needed to reduce redundant assignments while keeping the overload boundary in check. Secondly, an efficient and scalable scheduling framework for building and merging ANNS subgraphs remains unaddressed. Existing methods, such as DiskANN, often rely on a single high-cost machine to sequentially build and merge subgraphs, limiting scalability and efficiency. To address this, SPTAG ( Chen et al. 2018 ) employs a scalable k-NN graph construction method ( Wang et al. 2012 ) to partition datasets into non-overlapping subsets and distribute tasks across a cluster. However, as datasets grow in size and complexity, optimizing subgraph overlap for connectivity requires extensive iterations, leading to redundant computations and storage overhead. Observing that subgraph construction time is proportional to the size of its subset, an efficient scheduling framework can be designed to minimize construction time on a cluster without additional redundant computations, provided that overlap coverage and overload constraints are carefully addressed by a cost-effective data partitioning approach. To address these challenges, we introduce SOGAIC , the first S calable O verload-Aware G raph-Based A NNS I ndex C onstruction system, designed for ultra-large-scale vector databases exceeding 10 billion points. SOGAIC accelerates index construction through an adaptive data partitioning strategy coupled with a load-balancing task scheduling framework, ensuring scalability with computational resources while maintaining high-quality graph structures for efficient vector similarity search. 2. System Overview Figure 1. (a) Illustration of the assignment process for P1 and P2 based on their geometric relationships with centroids { C1 … C4 }. (b) Illustration of the deviation from P to P’ for the assignment process of P , when overload happens on division1. (c) Illustration of the overall data partitioning process for P with quantization encoding executed in parallel. Three diagrams The proposed system consists of two main stages. The first stage handles overlapped subsets division using an adaptive data partitioning algorithm while controlling overload bounds. The second stage schedules subgraph construction tasks across a distributed cluster and executes the agglomerative merging strategy to form the final ANNS graph index. Algorithm 1 Adaptive Overload-Aware Vector Assignment 0: Vector to be assigned \boldsymbol{\mathcal{V}} 0: Centroids from K-means c_{i}\in\boldsymbol{\mathcal{C}} 0: Max overlapping factor \boldsymbol{\Omega} >= 2 0: Adaptive relaxation parameter \epsilon > 1 0: Initialized sets for all centroids s_{i}\in\boldsymbol{\mathcal{S}} 0: Maximum assignable vectors of a set \boldsymbol{\Gamma} 1: Initialize: Create a priority queue Q <CentroidIndex, Dist> 2: for i=0 to |\boldsymbol{\mathcal{C}}|-1 do 3: Insert (i,\text{distance}(\boldsymbol{\mathcal{V}},c_{i})) into Q 4: end for 5: Initialize: curOLPCnt\leftarrow 0 ; curOLPFactor\leftarrow 0 6: Initialize: accDist\leftarrow 0 ; curAVGDist\leftarrow\infty 7: while Q is not empty and curOLPCnt < \boldsymbol{\Omega} 8: (\textbf{index},\textbf{dist})\leftarrow\textbf{ExtractMin}({\textbf{{Q}}}) 9: if dist <= \epsilon * curAVGDist 10: \textit{curOLPFactor}\leftarrow\textit{curOLPFactor}+1 11: \textit{accDist}\leftarrow\textit{accDist}+\textit{dist} 12: \textit{curAVGDist}\leftarrow\textit{accDist}/\textit{curOLPFactor} 13: if | s_{index} | < \boldsymbol{\Gamma} 14: \textit{curOLPCnt}\leftarrow\textit{curOLPCnt}+1 15: s_{index}\leftarrow s_{index}\cup\{\boldsymbol{\mathcal{V}}\} 16: else 17: curAVGDist\leftarrow\infty 18: end if 19: end if 20: end while 2.1. Overload-Aware Adaptive Data Partitioning The algorithm for partitioning the vector database into multiple overlapping subsets begins by determining the maximum number of base points per division, referred to as \boldsymbol{\Gamma} (capacity), which is constrained by the memory limits of each container in the computational cluster. Given a dataset containing \boldsymbol{N} (total points) and a maximum overlapping factor \boldsymbol{\Omega} (defining the maximum number of partitions a point can belong to), we can estimate the minimum number of partitions \boldsymbol{\Phi} (number of centroids) required to handle highly imbalanced data distributions effectively, which is: \boldsymbol{\Phi}=\lceil\boldsymbol{\Omega}\times\boldsymbol{N}/\boldsymbol{\Gamma}\rceil . After estimating \boldsymbol{\Phi} , we apply K-means clustering on a small sample of the dataset to obtain \boldsymbol{\Phi} centroids \boldsymbol{\mathcal{C}}=\{c_{1},c_{2},c_{3},\dots,c_{\boldsymbol{\Phi}}\} as the initial reference points for

Read the complete text