Brute-Force k-Nearest Neighbors Search on the GPU
University of California, Davis
Similarity Search and Applications, 2015
@article{li2015brute,
title={Brute-Force k-Nearest Neighbors Search on the GPU},
author={Li, Shengren and Amenta, Nina},
year={2015}
}
We present a brute-force approach for finding k-nearest neighbors on the GPU for many queries in parallel. Our program takes advantage of recent advances in fundamental GPU computing primitives. We modify a matrix multiplication subroutine in MAGMA library [6] to calculate the squared Euclidean distances between queries and references. The nearest neighbors selection is accomplished by a truncated merge sort built on top of sorting and merging functions in the Modern GPU library [3]. Compared to state-of-the-art approaches, our program is faster and it handles larger inputs. For instance, we can find 1000 nearest neighbors among 1 million 64-dimensional reference points at a rate of about 435 queries per second.
October 3, 2015 by hgpu
