Fast k nearest neighbor search using GPU

By Vincent Garcia, Eric Debreuve, Michel Barlaud. IEEE Computer Society Conference on Computer Vision and Pattern Recognition workshops, 2008

590 citations recorded by the source corpus.

Statistical measures coming from information theory represent interesting bases for image and video processing tasks such as image retrieval and video object tracking. For example, let us mention the entropy and the Kullback-Leibler divergence. Accurate estimation of these measures requires to adapt to the local sample density, especially if the data are high-dimensional. The k nearest neighbor (kNN) framework has been used to define efficient variable-bandwidth kernel-based estimators with such a locally adaptive property. Unfortunately, these estimators are computationally intensive since they rely on searching neighbors among large sets of d-dimensional vectors. This computational burden can be reduced by pre-structuring the data, e.g. using binary trees as proposed by the approximated nearest neighbor (ANN) library. Yet, the recent opening of graphics processing units (GPU) to general-purpose computation by means of the NVIDIA CUDA API offers the image and video processing community a powerful platform with parallel calculation capabilities. In this paper, we propose a CUDA implementation of the ldquobrute forcerdquo kNN search and we compare its performances to several CPU-based implementations including an equivalent brute force algorithm and ANN. We show a speed increase on synthetic and real data by up to one or two orders of magnitude depending on the data, with a quasi-linear behavior with respect to the data size in a given, practical range.

Subfields: Computer Vision and Pattern Recognition, Media Technology

View Paper: https://www.semanticscholar.org/paper/19d2b786fec5ded4d6cdca0e21f3c3f5264ecadf

How researchers see this paper

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

In Computer Vision and Pattern Recognition

In Media Technology

Citations in the corpus

kNN Query Processing in Metric Spaces Using GPUs (2011, methodology): “In [10], the final stage is implemented with a modified parallel insertion sort in order to just get the k closest elements, whereas in [13] authors used an improved Radix-sort.”
From Word Embeddings To Document Distances (2015, background): “The nearest neighbor search has a time complexity of O(p(2)), and it can be sped up further by leveraging out-of-the-box tools for fast (approximate or exact) nearest neighbor retrieval (Garcia et al., 2008; Yianilos, 1993; Andoni & Indyk, 2006).”
PuDianNao: A Polyvalent Machine Learning Accelerator (2015, background): “, [18]), the efficiency is limited, because they spend too many efforts on flexibly supporting diverse application domains.”
Fast GPU-based locality sensitive hashing for k-nearest neighbor computation (2011, background): “Garcia et al. [11] use GPUs to accelerate the brute-force k -nearest neighbor search.”
Context-aware saliency detection (2010, methodology): “One such implementation was introduced in [7] and [8], using NVIDIA’s C-based API Compute Unified Device Architecture (CUDA).”