GGNN: Graph-based GPU Nearest Neighbor Search

Abstract

Approximate nearest neighbor (ANN) search in high dimensions is an integral part of several computer vision systems and gains importance in deep learning with explicit memory representations. Since PQT, FAISS, and SONG started to leverage the massive parallelism offered by GPUs, GPU-based implementations are a crucial resource for today's state-of-the-art ANN methods. While most of these methods allow for faster queries, less emphasis is devoted to accelerating the construction of the underlying index structures. In this paper, we propose a novel GPU-friendly search structure based on nearest neighbor graphs and information propagation on graphs. Our method is designed to take advantage of GPU architectures to accelerate the hierarchical construction of the index structure and for performing the query. Empirical evaluation shows that GGNN significantly surpasses the state-of-the-art CPU- and GPU-based systems in terms of build-time, accuracy and search speed.

Stats

• citations60
• S2 citations—
• github stars0
• HF likes0
• heat score13.39
• arxiv keygroh2019ggnn

Related papers

• CAGRA: Highly Parallel Graph Construction And Approximate Nearest Neighbor Search For Gpus (2023)12.17
• Symphonyqg: Towards Symphonious Integration Of Quantization And Graph For Approximate Nearest Neighbor Search (2024)7.50
• Fusionanns: An Efficient CPU/GPU Cooperative Processing Architecture For Billion-scale Approximate Nearest Neighbor Search (2024)0.00
• Fast-convergent Proximity Graphs For Approximate Nearest Neighbor Search (2025)0.00
• A Real-time Adaptive Multi-stream GPU System For Online Approximate Nearest Neighborhood Search (2024)5.84
• EFANNA : An Extremely Fast Approximate Nearest Neighbor Search Algorithm Based On Knn Graph (2016)0.00
• A Comprehensive Survey And Experimental Comparison Of Graph-based Approximate Nearest Neighbor Search (2021)17.35
• Billion-scale Similarity Search With Gpus (2017)24.96