GPU-FS-<em>k</em>NN: A Software Tool for Fast and Scalable <em>k</em>NN Computation Using GPUs

<div><h3>Background</h3><p>The analysis of biological networks has become a major challenge due to the recent development of high-throughput techniques that are rapidly producing very large data sets. The exploding volumes of biological data are craving for extreme computational power and special computing facilities (i.e. super-computers). An inexpensive solution, such as General Purpose computation based on Graphics Processing Units (GPGPU), can be adapted to tackle this challenge, but the limitation of the device internal memory can pose a new problem of scalability. An efficient data and computational parallelism with partitioning is required to provide a fast and scalable solution to this problem.</p> <h3>Results</h3><p>We propose an efficient parallel formulation of the <em>k</em>-Nearest Neighbour (<em>k</em>NN) search problem, which is a popular method for classifying objects in several fields of research, such as pattern recognition, machine learning and bioinformatics. Being very simple and straightforward, the performance of the <em>k</em>NN search degrades dramatically for large data sets, since the task is computationally intensive. The proposed approach is not only fast but also scalable to large-scale instances. Based on our approach, we implemented a software tool GPU-FS-<em>k</em>NN (GPU-based Fast and Scalable <em>k</em>-Nearest Neighbour) for CUDA enabled GPUs. The basic approach is simple and adaptable to other available GPU architectures. We observed speed-ups of 50–60 times compared with CPU implementation on a well-known breast microarray study and its associated data sets.</p> <h3>Conclusion</h3><p>Our GPU-based Fast and Scalable <em>k</em>-Nearest Neighbour search technique (GPU-FS-<em>k</em>NN) provides a significant performance improvement for nearest neighbour computation in large-scale networks. Source code and the software tool is available under GNU Public License (GPL) at <a href="https://sourceforge.net/p/gpufsknn/">https://sourceforge.net/p/gpufsknn/</a>.</p>