Fast approximate k-nearest neighbours search using GPGPU

Niko Lukac, Borut Zalik
Faculty of electrical engineering and computer science, University of Maribor, Smetanova ulica 17, SI-2000 Maribor, Slovenia
Symposium on GPU Computing and Applications (GPUAPP 2013), 2013


   title={Fast approximate k-nearest neighbours search using GPGPU},

   author={Luka{v{c}}, Niko and {v{Z}}alik, Borut},



Source Source   



The k-nearest neighbours (k-NN) search is one of the most critical nonparametric methods used in data retrieval and similarity tasks. Over recent years fast k-NN processing for large amount of high-dimensional data is increasingly demanded. Locality-sensitive hashing is a viable solution for computing fast approximate nearest neighbours (ANN) with reasonable accuracy. This chapter presents a novel parallelization of the locality-sensitive hashing method using GPGPU, where the multi-probe variant is considered. The method was implemented using CUDA platform for constructing a k-ANN graph. It was compared to the state-of-the-art CPU-based k-ANN and two GPU-based k-NN methods on large and multidimensional dataset. The experimental results showed that the proposed method has a speedup of 30x or higher, in comparison to the CPU-based approximate method, whilst retaining a high recall rate.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2020 hgpu.org

All rights belong to the respective authors

Contact us: