Improving the speed and stability of the k-nearest neighbors method

We present an efficient technique to accelerate the classical k-nearest neighbors method. The idea is to replace the sort operation with calculating the order statistics. This makes the kNN method not only more efficient, but also increases its stability with respect to the order in which the data is presented to the algorithm. We illustrate the gain in performance on numerical examples. We compare the efficiency of the brute force approach to kNN on Graphics Processing Units with kd-trees, and confirm superiority of the proposed approach.

► The kNN method is accelerated by using order statistics and avoiding the sort operation. ► kNN is not stable with respect to the order in which the data are presented. We solve this problem. ► Brute force kNN was implemented on GPU. It is significantly faster than kd-trees on CPU.