Fast and memory efficient implementation of the exact PNN

Abstract

Straightforward implementation of the exact pairwise nearest neighbor (PNN) algorithm takes O(N3) time, where N is the number of training vectors. This is rather slow in practical situations. Fortunately, much faster implementation can be obtained with rather simple modifications to the basic algorithm. In this paper, we propose a fast O(tauN2) time implementation of the exact PNN, where tau is shown to be significantly smaller than N, We give all necessary data structures and implementation details, and give the time complexity of the algorithm both in the best case and in the worst case. The proposed implementation achieves the results of the exact PNN with the same O(N) memory requirement.