Brute-Force k-Nearest Neighbors Search on the GPU

Shengren Li, Nina Amenta
University of California, Davis
Similarity Search and Applications, 2015


   title={Brute-Force k-Nearest Neighbors Search on the GPU},

   author={Li, Shengren and Amenta, Nina},



Download Download (PDF)   View View   Source Source   



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.
Rating: 2.5/5. From 3 votes.
Please wait...

* * *

* * *

HGPU group © 2010-2024 hgpu.org

All rights belong to the respective authors

Contact us: