Fast $k$-NNG construction with GPU-based quick multi-select

Ivan Komarov, Ali Dashti, Roshan D'Souza

In this paper we describe a new brute force algorithm for building the $k$-Nearest Neighbor Graph ($k$-NNG). The $k$-NNG algorithm has many applications in areas such as machine le…