Efficient Selection Algorithm for Fast k-NN Search on GPUs

By Xiaoxin Tang, Zhiyi Huang, D. Eyers, S. Mills, Minyi Guo. 2015

18 citations recorded by the source corpus.

k Nearest Neighbours (k-NN) search is a fundamental problem in many computer vision and machine learning tasks. These tasks frequently involve a large number of high-dimensional vectors, which require intensive computations. Recent research work has shown that the Graphics Processing Unit (GPU) is a promising platform for solving k-NN search. However, these search algorithms often meet a serious bottleneck on GPUs due to a selection procedure, called k-selection, which is the final stage of k-NN and significantly affects the overall performance. In this paper, we propose new data structures and optimization techniques to accelerate k-selection on GPUs. Three key techniques are proposed: Merge Queue, Buffered Search and Hierarchical Partition. Compared with previous works, the proposed techniques can significantly improve the computing efficiency of k-selection on GPUs. Experimental results show that our techniques can achieve an up to 4:2× performance improvement over the state-of-the-art methods.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Efficiency & Compression, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Efficiency & Compression

In Signal Processing

Citations in the corpus

Billion-Scale Similarity Search with GPUs (2017, methodology): “Other more novel GPU algorithms are available for small k, namely the selection algorithm in the fgknn library [41].”