Analysis of Parallel K-Limit Selection Sort Based K Nearest Neighbors for Image Classification

The K-Nearest Neighbors(K-NN) algorithm is one of the basic supervised algorithm that is a widely used classification technique in the field of Image Classification, data mining and test classification. However, K-NN is not an efficient algorithm when the dataset is too big due to the computation overhead of distance calculations and sorting. The bottleneck for K-NN is distance calculations and sorting. This paper analyses the performance of parallel version of K-limit Selection sort based k nearest neighbours algorithm. The distance calculations of K-NN is implemented utilizing the CUDA multi-threading model and CUDA streams. The Parallel K-NN is evaluated with Manhattan and euclidean distance metric for performance analysis. To evaluate the performance of the parallel k-NN algorithm, the benchmark data set: MNIST handwritten dataset is used for different configurations. The K-limit parallel selection sort-based K-NN algorithm outperformed the serial K-NN algorithm, achieving significant speed-up up to 77X with the Manhattan metric and 61X with the Euclidean metric for the MNIST dataset.