Fast and memory efficient implementation of the exact PNN
P Fränti1, T Kaukoranta, D F Shen
1Department of Computer Science, University of Joensuu, FIN-80101 Joensuu, Finland.
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.
Related Concept Videos
Fast Fourier Transform
The computational efficiency of the FFT becomes...
Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
Insensitive Nuclei Enhanced by Polarization Transfer (INEPT)
Linear Approximations
Interpreting ¹H NMR Signal Splitting: The (n + 1) Rule
Binomial Expansion Using Pascal's Triangle

