Fast k nearest neighbor search
using GPU

Illustration of the distance to the 2^nd nearest neighbor (red dot = points, blue circle = distance to the 2-NN).

Fast k nearest neighbor search using GPU

Authors

• Vincent Garcia
• Eric Debreuve
• Michel Barlaud

Abstract

The k-nearest neighbor (kNN) search is a problem found in many research and industrial domains such as 3-dimensional object rendering, content-based image retrieval, statistics (estimation of entropies and divergences), biology (gene classification), etc. In spite of some improvements in the last decades, the computation time required by the kNN search still remains the bottleneck of methods based on kNN, especially in high dimensionnal spaces.
We propose in this website two GPGPU implementations of the brute-force (exhaustive) kNN search algorithm. These implementations, through the APIs NVIDIA CUDA and NVIDIA CUBLAS, paralellize the kNN search process into the computer graphic card. Thanks to the parallel structure of the GPU and the optimization of the APIs, the proposed implementation appears to be much faster, especially in high dimension and for large dataset, than the celebrated and highly optimized ANN C++ library.

References

Following the terms of the license below, you need to acknowledge the use of this code. Do so by referencing the following article.

1. V. Garcia and E. Debreuve and M. Barlaud. Fast k nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008
   Preprint Bibtex DOI IEEE explore
   @INPROCEEDINGS{Garcia_2008_CVGPU,
       author = {V. Garcia and E. Debreuve and M. Barlaud},
       title = {Fast k nearest neighbor search using GPU},
       booktitle = {CVPR Workshop on Computer Vision on GPU},
       year = {2008},
       address = {Anchorage, Alaska, USA},
       month = {June}
   }
2. Vincent Garcia. Ph.D. Thesis: Suivi d'objets d'intérêt dans une séquence d'images : des points saillants aux mesures statistiques Université de Nice - Sophia Antipolis, Sophia Antipolis, France, December 2008
   Thesis Bibtex
   @PHDTHESIS{Garcia_2008_PHD,
       author = {Vincent Garcia},
       title = {Suivi d'objets d'intérêt dans une séquence d'images : des points saillants aux mesures statistiques},
       school = {Université de Nice - Sophia Antipolis},
       address = {Sophia Antipolis, France},
       month = {December},
       year = {2008}
   }

Obtaining the CUDA source code (release 2010/01/27)

Versions

The provided CUDA code is usable both for C, and Matlab program. Please read the README file to learn how to adapt code. We provide 4 implementations of the kNN search to fit to your needs:

• KNN CUDA — implementation CUDA of the k-nearest neighbor search.
• KNN CUBLAS — implementation CUBLAS of the k-nearest neighbor search. This version is usually faster than KNN CUDA and is based on matrix multiplication to compute the distances between points.
• With indexes — provides for each query point the distances to the k nearest neighbors and the indexes of these neighbors.
• Without indexes — provides for each query point only the distance to the k-th nearest neighbor. This version is faster than the version with indexes because first it uses less memory and second it does not spent time on processing indexes.

Download the code

KNN CUDA without indexes KNN CUDA with indexes KNN CUBLAS without indexes KNN CUBLAS with indexes

License

The provided code is licensed under a Creative Commons Attribution-Share Alike 3.0 Unported License. You are free:

• to Share — to copy, distribute and transmit the work,
• to Remix — to adapt the work,

Under the following conditions:

• Attribution — You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).
• Noncommercial — You may not use this work for commercial purposes.
• Share Alike — If you alter, transform, or build upon this work, you may distribute the resulting work only under the same or similar license to this one.