On the Effectiveness of Graph Reordering for Accelerating Approximate Nearest Neighbor Search on GPU
This work addresses memory layout optimization for GPU-based ANNS, which is incremental as it builds on existing algorithmic innovations.
The paper tackles the problem of accelerating graph-based approximate nearest neighbor search on GPUs by investigating graph reordering effects, achieving up to 15% QPS improvements while preserving search accuracy.
We present the first systematic investigation of graph reordering effects for graph-based Approximate Nearest Neighbor Search (ANNS) on a GPU. While graph-based ANNS has become the dominant paradigm for modern AI applications, recent approaches focus on algorithmic innovations while neglecting memory layout considerations that significantly affect execution time. Our unified evaluation framework enables comprehensive evaluation of diverse reordering strategies across different graph indices through a graph adapter that converts arbitrary graph topologies into a common representation and a GPU-optimized graph traversal engine. We conduct a comprehensive analysis across diverse datasets and state-of-the-art graph indices, introducing analysis metrics that quantify the relationship between structural properties and memory layout effectiveness. Our GPU-targeted reordering achieves up to 15$\%$ QPS improvements while preserving search accuracy, demonstrating that memory layout optimization operates orthogonally to existing algorithmic innovations. We will release all code upon publication to facilitate reproducibility and foster further research.