Efficient K-Nearest Neighbor Search using JIT

A small but efficient tool to perform KNN search

Description

This is a small but efficient tool to perform K-nearest neighbor search, which has wide Science and Engineering applications, such as pattern recognition, data mining and signal processing.

The code was initially implemented through vectorization. After discussions with John D'Errico, I realized that my algorithm will suffer numerical accurancy problem for data with large values. Then, after trying several approaches, I found simple loops with JIT acceleration is the most efficient solution. Now, the performance of the code is comparable with kd-tree even the latter is coded in a mex file.

The code is very simple, hence is also suitable for beginner to learn knn search.

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
distance.m, KD Tree Nearest Neighbor and Range Search, NEARESTPOINT, nearestneighbour.m, IPDM: Inter-Point Distance Matrix

• MATLAB release: MATLAB 7.5 (R2007b)

[Luigi Giaccari]

I think someone, maybe not the author, is faking the download number.
My opinion is that this is a very usefull routine, very well commented and totally m-coded.
The performances of course can not be the ones declared in the presentation. The algorithm it is just a brute search can only be competitive against kd-tree data structure for a small number of search and reference points.
For KNN search is used the sort function to find K-neighbours, and this is a very brute algorithm. I Know this the fastest m-code way to find KNN, but it is clear
that kd-trees will overcome this algorithm for very small models.

[V. Poor]