GLIDE: GPU-Accelerated ANN Graph Index Construction via Data Locality

Graph-based ANN indexes offer state-of-the-art search performance, but suffer from prohibitively long construction times on CPUs. Although recent studies leverage GPU parallelism to accelerate graph construction, they still face key limitations, including redundant computations and poor scalability. To address these issues, we propose GLIDE, a GPUaccelerated graph construction method that leverages data locality. First, GLIDE adopts a locality-aware partitioning strategy to better group vectors, and designs a fine-grained parallel paradigm to efficiently construct high-locality sub-graphs. These sub-graphs allow most nodes to connect with their neighbors, dramatically reducing redundancy. Second, GLIDE presents a lightweight merging technique that treats boundary points as key connectors, which completely eliminates ANN searches during merging. Since all phases of construction operate without all vectors into GPU memory, GLIDE scales effectively to large-scale vector datasets. Third, by leveraging the enhanced data locality, GLIDE further introduces a query-aware search algorithm that restricts the search space to regions likely to contain relevant neighbors, improving search efficiency. Comprehensive experiments demonstrate that, compared to state-of-the-art method, GLIDE achieves up to $3.0 \times$ faster construction while delivering competitive search performance. Notably, GLIDE constructs a graph index for SIFT100M in just 13 minutes, and the average query latency is $3 \mu ~\mathrm{s}$ at recall@10 of 95%.