Source-linked AI summary
Fast k Nearest Neighbor Search using GPU
Vincent Garcia, Eric Debreuve, Michel Barlaud
TL;DR
KNN supports applications such as classification and statistical estimation, but exhaustive computation becomes costly as data size grows. The paper implements KNN using NVIDIA CUDA to exploit GPU parallelism. BF-CUDA is reported to accelerate KNN by up to 120 times, with performance depending on the implementation and problem dimensions.
Problem
KNN is used in many applications, but its computation burden grows with data size and can make search a bottleneck.
Method
The paper implements brute-force KNN search with NVIDIA CUDA on a GPU to exploit the method’s parallelizable distance and sorting operations.
Results
BF-CUDA is up to 120 times faster than BF-Matlab, 100 times faster than BF-C, and 40 times faster than KDT-C.
Takeaways & Limitations
CUDA-based KNN reduces the size restriction needed for reasonable-time search in KNN-based content-based image retrieval.
Abstract
from arXiv · showhide
The recent improvements of graphics processing units (GPU) offer to the computer vision community a powerful processing platform. Indeed, a lot of highly-parallelizable computer vision problems can be significantly accelerated using GPU architecture. Among these algorithms, the k nearest neighbor search (KNN) is a well-known problem linked with many applications such as classification, estimation of statistical properties, etc. The main drawback of this task lies in its computation burden, as it grows polynomially with the data size. In this paper, we show that the use of the NVIDIA CUDA API accelerates the search for the KNN up to a factor of 120.
0.1 Introduction
GPU advances provide a powerful platform for parallel computing, while KNN remains a computationally demanding problem used across statistics, classification, filtering, and computer vision.
- GPU and KNN motivation: GPUs are specialized for parallel computing and can accelerate many computer vision algorithms.NVIDIA CUDA provides a C-based API for using GPU parallel performance in non-graphics applications.
- GPU and KNN motivation: KNN supports applications including density estimation, classification, image filtering, and high-dimensional statistical estimation.
0.2 k Nearest Neighbors Search
KNN finds the closest reference points for each query under a chosen distance, but exhaustive search has high complexity. Its importance follows from applications where KNN can become a computational bottleneck.
- Problem definition: KNN searches for the k nearest reference points to every query point in a shared d-dimensional space using a specified distance.Euclidean and Manhattan distances are common, but infinity-norm and Mahalanobis distances are also possible.
- Brute-force search: Brute-force search computes every query-reference distance, sorts each distance list, selects the k smallest, and repeats for all queries.
- Complexity: O(nmd) distance computation and O(nm log m) sorting make brute-force KNN computationally expensive.The distance calculations require approximately 2nmd additions/subtractions and nmd multiplications.
- Alternative methods: Alternative methods reduce computation by partitioning the space and evaluating distances only within selected nearby volumes.Experiments reported in the passage find one such method three times faster than brute force.
- Applications: KNN frequently becomes a bottleneck in graphics and non-graphics applications, motivating faster search methods.The section identifies three applications using KNN, including entropy estimation.
0.2. K NEAREST NEIGHBORS SEARCH 5
KNN underlies entropy estimation, classification, clustering, and content-based image retrieval. These applications use nearest-neighbor distances or labels, but computation time can restrict descriptor dimensionality in image retrieval.
- Entropy estimation: Entropy estimators use distances to nearest neighbors, including the distance to each point’s k-th nearest neighbor.
- Classification and clustering: KNN classification assigns each query item the category most represented among its k closest training examples.Larger k values provide smoothing that reduces vulnerability to noise, while increasing computation time.
- Content-based image retrieval: Content-based image retrieval searches large image databases using image contents such as colors, shapes, and textures.
- Content-based image retrieval: A KNN-based image-retrieval pipeline extracts query keypoints, computes descriptors, and searches database descriptors for the k closest matches.A voting algorithm then determines the most likely image.
- Content-based image retrieval: Descriptor sizes in content-based image retrieval are typically restricted to 9–128 to maintain reasonable computation time.The search for closest descriptors is itself a KNN problem and contributes to the application’s computation time.
0.3 Experiments
The experiments compare MATLAB, C, and CUDA implementations of brute-force KNN with a C kd-tree implementation. They evaluate computation time across point-set sizes and space dimensions with k set to 20.
- Compared implementations: The study compares BF-Matlab, BF-C, BF-CUDA, and KDT-C implementations of KNN search.KDT-C uses the ANN C library, while the brute-force variants differ by implementation platform.
- Experimental setup: The measured computation time depends on reference-set size, query-set size, and space dimension.The experiments set k to 20; brute-force time is unaffected by k, whereas KDT-C time increases with k.
0.3. EXPERIMENTS 7
The experiments compare BF-Matlab, BF-C, KDT-C, and BF-CUDA, showing substantial CUDA speedups and low sensitivity to point dimension, with data-transfer costs limiting performance in low dimensions.
- Experimental setup: The experiments use computation times in seconds for typical KNN point-set sizes and dimensions, comparing three BF implementations with one kd-tree method.The implementations are BF-Matlab, BF-C, BF-CUDA, and KDT-C.
- Comparison of methods: BF-CUDA is up to 120 times faster than BF-Matlab, 100 times faster than BF-C, and 40 times faster than KDT-C.For 38400 reference and query points in 96 dimensions, BF-CUDA takes 43 seconds versus approximately one hour for BF-Matlab and BF-C and 20 minutes for KDT-C.
- Dimension sensitivity: For N = 4800, computation time increases linearly with point dimension, but BF-CUDA has a quasi-null slope of 0.001.The slopes are 0.56 for BF-Matlab, 0.48 for BF-C, and 0.20 for KDT-C.
- Dimension sensitivity: For N = 38400, the slopes are 34 for BF-C, 31 for BF-Matlab, 14 for KDT-C, and 0.14 for BF-CUDA.Thus, the CUDA implementation remains much less sensitive to space dimension in this experiment.
- Performance boundary: With D = 8 and N = 19200 or N = 38400, KDT-C is fastest because BF-CUDA spends most of its time copying data between CPU and GPU memory.For D > 8, BF-CUDA becomes the most interesting implementation despite memory-transfer costs.
0.3. EXPERIMENTS 9
Computation time increases linearly with point dimension for BF-Matlab, BF-C, BF-CUDA, and KDT-C, but the increase is quasi-null for BF-CUDA.
- Computation time increases linearly with point dimension for all four methods.The compared methods are BF-Matlab, BF-C, BF-CUDA, and KDT-C.
- BF-CUDA shows a quasi-null increase in computation time as point dimension grows.
0.4 Conclusion
The paper proposes a GPU implementation of k nearest neighbors search and reports that NVIDIA CUDA accelerates KNN resolution by up to a factor of 120.
- The paper proposes a fast k nearest neighbors search implementation using a graphics processing unit.
- NVIDIA CUDA accelerates KNN resolution by up to a factor of 120.The improvement reduces the size restriction generally needed for reasonable-time KNN searches in content-based image retrieval applications.