K nearest neighbor search

Lightning fast k nearest neighbor search, yet very simple.

Description

This is just a brute force implementation of k nearest neighbor search without using any fancy data structure, such as kd-tree. However it is the fastest knn matlab implementation I can find.

A partial sort mex function is implemented which is a simple wrapper of c++ partial_sort.

Provided the sort function, the matlab code is only of two lines. However, it is extremely fast.

install:
build;

usage:
[distance, index] = knn(query,data,k);

example:
X=rand(200,2000);Y=rand(200,5000);
tic;[D,N]=knn(X,Y,50);toc

• MATLAB release: MATLAB 7.11 (2010b)

[David Liu]

Fail to compile:
lcc preprocessor error: top.cpp:2 Could not find include file <algorithm>
lcc preprocessor error: top.cpp:3 Could not find include file <vector>
lcc preprocessor warning: top.cpp:49 No newline at end of file

[Yuval]

Worked with older compilers but with MS Visual Studio 2010 I get:

C:\Program Files (x86)\Microsoft Visual Studio 10.0\VC\INCLUDE\yvals.h(576) : error C2371: 'char16_t' : redefinition; different basic types
        c:\program files\matlab\r2010a\extern\include\matrix.h(330) : see declaration of 'char16_t'
psort.cpp(22) : warning C4267: 'initializing' : conversion from 'size_t' to 'int', possible loss of data
psort.cpp(23) : warning C4267: 'initializing' : conversion from 'size_t' to 'int', possible loss of data

Please fix !!!

[Venkat R]

Dear Chen,
Can you help add the feature of chi-square as metric, instead of euclidean distance.

with regards,
Ramana

[Jakob Wilm]

This implementation of brute force nearest neighbor search is quite fast for small data sets of high dimensionality. In many other cases however, KDTreeSearcher and ExhaustiveSearcher in Matlabs Statistics Toolbox is faster.

[Mo Chen]

KDTree is only suitable for low dimensional data. for very high dimensional data, it sucks big time.