K-nearest neighbor search: Fast GPU-based implementations and application to high-dimensional feature matching

Vincent Garcia, Eric Debreuve, Frank Nielsen, Michel Barlaud

Abstract

The k-nearest neighbor (kNN) search problem is widely used in domains and applications such as classification, statistics, and biology. In this paper, we propose two fast GPU-based implementations of the brute-force kNN search algorithm using the CUDA and CUBLAS APIs. We show that our CUDA and CUBLAS implementations are up to, respectively, 64X and 189X faster on synthetic data than the highly optimized ANN C++ library, and up to, respectively, 25X and 62X faster on high-dimensional SIFT matching.
BibTeX
@inproceedings{garcia2010k,
  author = {Vincent Garcia and Eric Debreuve and Frank Nielsen and Michel Barlaud},
  title = {{K-nearest neighbor search: Fast GPU-based implementations and application to high-dimensional feature matching}},
  booktitle = {ICIP},
  year = {2010},
  doi = {10.1109/icip.2010.5654017},
}

Loading related content...

Figure