3.66667
3.7 | 3 ratings Rate this file 42 Downloads (last 30 days) File Size: 1.96 KB File ID: #28897

K nearest neighbor search

by

Mo Chen (view profile)

 

30 Sep 2010 (Updated )

Lightning fast k nearest neighbor search, yet very simple.

| Watch this File

File Information
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 (R2010b)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (6)
12 May 2014 yao

yao (view profile)

 
07 Feb 2012 Mo Chen

Mo Chen (view profile)

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

Comment only
05 Nov 2011 Jakob Wilm

Jakob Wilm (view profile)

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.

21 Oct 2011 Venkat R

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

with regards,
Ramana

Comment only
09 Feb 2011 Yuval

Yuval (view profile)

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 !!!

08 Jan 2011 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

Comment only
Updates
15 Oct 2010

modify description

29 Oct 2010

reimplemented and fix a bug

02 Nov 2010

change the sorting method from nth_element to partial_sort

Contact us