The demand for Graphical Processing Units or GPUs, gained a tremendous hike during the past few years as a result of its migration from processing and representation of mere high dimensional graphical patterns to a heterogeneous high performance computing capability. The future generation data science requirements like Big Data Analysis and Deep Learning increased the popularity of GPUs to a wide extend. Graphical Processing Units or GPUs are well suited for parallel processing which enables visualization of vast amount of real time processed data in a more significant manner than CPU. From processing mere graphical algorithms, GPU has gone through numerous advancements in the past few decades. They can be used to improve the performance and efficiency of any algorithm nowadays. The expenditure of installation and use of GPUs have come down to a great extent from the initial huge amount. Data classification tasks like kNN classification can be done more efficiently and cost effectively by applying parallelism using GPU. kNN algorithms are the most popular data classification algorithm, because of its simplicity, high accuracy and versatility. This paper studies four major kNN algorithms developed for GPU processing and compares the techniques and methodologies used in them.

GPU, BF CUDA, CUBLAS, CUKNN

[1] Han, Jiawei, Jian Pei, and Micheline Kamber. “Data mining: concepts and techniques”. Elsevier, 2011.
[2] Yigit, Halil. "A weighting approach for KNN classifier". Electronics, Computer and Computation (ICECCO), International Conference on. IEEE, 2013.
[3] Zhang, Shichao, et al. "Efficient knn classification with different numbers of nearest neighbors". IEEE transactions on neural networks and learning systems 29.5, 2018.
[4] Ma, Hongxing, Jianping Gou, Xili Wang, Jia Ke, and Shaoning Zeng. "Sparse Coefficient-Based k-Nearest Neighbor Classification." IEEE Access 5: 16618-16634, 2017.
[5] Buck, Ian. "Gpu computing: Programming a massively parallel processor." International Symposium on IEEE, 2007.
[6] NVIDIA CUDA C Programming Guide Version 4.2, 2012.
[7] Zhang, Min-Ling, and Zhi-Hua Zhou. "ML-KNN: A lazy learning approach to multi-label learning." Pattern recognition , 2007.
[8] Bauce, M., et al. "The GAP project-GPU for real-time applications in high energy physics and medical imaging." 19th IEEE-NPSS Real Time Conference. IEEE, 2014.
[9] McClanahan, Chris. "History and evolution of gpu architecture." A Survey Paper, 2010.
[10] Kim, Youngsok, Jaewon Lee, Donggyu Kim, and Jangwoo Kim. "ScaleGPU: GPU architecture for memory-unaware GPU programming." IEEE Computer Architecture Letters, 2014.
[11] Delgado, Jaime, Gabriel Martín, Javier Plaza, Luis-Ignacio Jiménez, and Antonio Plaza. "On the optimization of memory access to increase the performance of spatial preprocessing techniques on graphics processing units." IEEE International Geoscience and Remote Sensing Symposium, 2016.
[12] Garcia, Vincent, Eric Debreuve, and Michel Barlaud. "Fast k nearest neighbor search using GPU." at arXiv preprint arXiv:0804.1448 , 2008.
[13] Kuang, Quansheng, and Lei Zhao. "A practical GPU based kNN algorithm." Proceedings. The International Symposium on Computer Science and Computational Technology (ISCSCI 2009). Academy Publisher, 2009.
[14] Garcia, Vincent, et al. "K-nearest neighbor search: Fast GPU-based implementations and application to high-dimensional feature matching." Image Processing (ICIP), 17th IEEE International Conference, 2010.
[15] Liang, Shenshen, et al. "Design and evaluation of a parallel k-nearest neighbor algorithm on CUDA-enabled GPU." Web Society (SWS), IEEE 2nd Symposium, 2010.