Fabian Groh^1,2, Lukas Ruppert¹, Patrick Wieschollek^1,2, Hendrik P. A. Lensch^1
1University of Tübingen, ²Amazon Tübingen
IEEE Transactions on Big Data

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.

Paper [PDF] (author's version) [arXiv] (author's version) [IEEE TBD] (published version)
Code [GitHub]

@ARTICLE{groh2022ggnn,
  author={Groh, Fabian and Ruppert, Lukas and Wieschollek, Patrick and Lensch, Hendrik},
  journal={IEEE Transactions on Big Data},
  title={GGNN: Graph-based GPU Nearest Neighbor Search},
  year={2023},
  volume={9},
  number={1},
  pages={267-279},
  doi={10.1109/TBDATA.2022.3161156}
}

This work has been partially funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC number 2064/1 - Project number 390727645 and SFB 1233, TP 02 - Project number 276693517. It was supported by the German Federal Ministry of Education and Research (BMBF): Tübingen AI Center, FKZ: 01IS18039A.