14622

Brute-Force k-Nearest Neighbors Search on the GPU

Shengren Li, Nina Amenta
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}

}

Download Download (PDF)   View View   Source Source   

1137

views

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.
VN:F [1.9.22_1171]
Rating: 5.0/5 (3 votes cast)
Brute-Force k-Nearest Neighbors Search on the GPU, 5.0 out of 5 based on 3 ratings

* * *

* * *

HGPU group © 2010-2017 hgpu.org

All rights belong to the respective authors

Contact us: