Abstract
Approximate Nearest Neighbor Search (ANNS) plays a critical role in variousdisciplines spanning data mining and artificial intelligence, from informationretrieval and computer vision to natural language processing and recommendersystems. Data volumes have soared in recent years and the computational cost ofan exhaustive exact nearest neighbor search is often prohibitive, necessitatingthe adoption of approximate techniques. The balanced performance and recall ofgraph-based approaches have more recently garnered significant attention inANNS algorithms, however, only a few studies have explored harnessing the powerof GPUs and multi-core processors despite the widespread use of massivelyparallel and general-purpose computing. To bridge this gap, we introduce anovel parallel computing hardware-based proximity graph and search algorithm.By leveraging the high-performance capabilities of modern hardware, ourapproach achieves remarkable efficiency gains. In particular, our methodsurpasses existing CPU and GPU-based methods in constructing the proximitygraph, demonstrating higher throughput in both large- and small-batch searcheswhile maintaining compatible accuracy. In graph construction time, our method,CAGRA, is 2.2~27x faster than HNSW, which is one of the CPU SOTAimplementations. In large-batch query throughput in the 90% to 95% recallrange, our method is 33~77x faster than HNSW, and is 3.8~8.8x faster than theSOTA implementations for GPU. For a single query, our method is 3.4~53x fasterthan HNSW at 95% recall.