high performance computing on graphics processing units: hgpu.org

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.