3.66667

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

K nearest neighbor search

by

 

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  
07 Feb 2012 Mo Chen

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

05 Nov 2011 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.

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

09 Feb 2011 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 !!!

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

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