Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1109/IPDPS.2015.115 | International Parallel & Distributed Processing Symposium |
Keywords | Field | DocType |
k-NN, k-selection, GPUs, Merge Queue, Buffered Search, Hierarchical Partition | Bottleneck,Data structure,Search algorithm,Computer science,Parallel computing,Selection algorithm,Beam search,Graphics processing unit,Best-first search,Performance improvement | Conference |
ISSN | Citations | PageRank |
1530-2075 | 4 | 0.47 |
References | Authors | |
15 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xiaoxin Tang | 1 | 10 | 2.60 |
| Zhiyi Huang | 2 | 91 | 19.14 |
| David M. Eyers | 3 | 477 | 45.90 |
| Steven Mills | 4 | 41 | 17.74 |
| Minyi Guo | 5 | 3969 | 332.25 |