AGC: A Unified Architecture for Accelerating K-Nearest Neighbor Graph Construction in Vector Search

The advancements in learning-based embedding models have propelled the embedding vector to become a vital data structure for various semantic search applications. The graph-based vector search method, which relies on the k-nearest neighbor (k-NN) graph, has gained immense popularity due to its superior performance in recall and throughput compared to other vector search methods. However, the construction of the k-NN graph is a time-consuming process, which not only affects the efficiency of identifying the optimal k-NN graph but also impacts data updates, especially for large-scale vector datasets. Despite the availability of various software-level optimization methods, such as iterative, refinement, and incremental methods, their peak performance is still limited to the underlying CPU platform. Furthermore, the existing GPU and specialized accelerator solutions only focus on partial k-NN graph construction methods and still encounter low efficiency when executing iterative methods due to irregular memory access, low data reuse, and redundant distance calculations.