SCIENCE@home

Efficient Selection Algorithm for Fast k-NN Search on GPUs

Xiaoxin Tang,Zhiyi Huang,D. Eyers,S. Mills,M. Guo

Published 2015 in IEEE International Parallel and Distributed Processing Symposium

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.

PUBLICATION RECORD

  • Publication year

    2015

  • Venue

    IEEE International Parallel and Distributed Processing Symposium

  • Publication date

    2015-05-01

  • Fields of study

    Computer Science

  • Identifiers
    DOI 10.1109/IPDPS.2015.115
  • External record

    Open on Semantic Scholar

  • Source metadata

    Semantic Scholar

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY

Showing 1-16 of 16 citing papers · Page 1 of 1