Scalable Distributed Index Construction for Large-Scale Graph-Based ANNS
摘要
In high-dimensional vector spaces, approximate nearest neighbor search (ANNS) is essential for modern database and AI systems. Graph-based ANNS has become increasingly popular owing to its balance between search efficiency and accuracy. However, building indexes for extremely large graphs remains challenging: single-node index construction can take a long time (days or even weeks) due to limited memory, computation, and I/O resources, while distributed index construction suffers from workload imbalance, network and I/O bottlenecks during index merging, and poor hardware utilization. This paper presents SD-GAC, a scalable distributed index construction framework for large-scale graph-based ANNS. SD-GAC introduces a fine-grained partitioning and packing scheme to ensure balanced distribution of index construction workloads, a communication-efficient merging algorithm that prefetches and batches all required neighbor data in a single pass, and a NUMA-aware construction algorithm that maximizes local memory and cache utilization. Evaluation shows that SD-GAC significantly reduces index construction time and achieves near-linear speedup with increasing computational resources.