K-Nearest Neigbors and Radius (Range) Search

August 7, 2009 by Luigi Giaccari 
Filed under: Algorithms, Computational Geometry, Mathematics 
2 Comments
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)
VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)

KNN Graph

BruteSearchMex

When the dataset is small, when you have to run only a few number of search, or when the dimensions of points is large, the brute search method is still faster than kd-trees data structure. Computing the distances one by one take a minor time than building the tree.
Some of this problems have became less gravous since the introduction of GLTree (file id 22190) which allows for a very fast tree construction.
Despite this, very small dataset are still terrain for brute search algorithms.

I saw many k-neighbours utilities on FEX, but all them were m-coded. I think such a brute calculation is not an m-code job. So I developed my own Nearest Neighbour finder. It is nothing special it just computes all the distances and take the ones required from the input parameters, but of course the mex implementation make it even faster than vectorized m-code.

The following utilities are provided:

  • Nearest neighbor
  • K-Nearest neighbors
  • Radius Search

They al supports N-dimensions and work on double, it is possible to choose if return the distances.

Here is a time comparison with a vectrized m-code:

N=1000000;%number of reference points
Nq=100;%number of query points
dim=3;%dimension of points
k=3;%number of neighbor

tic
[idc,dist]=BruteSearchMex(p',qp','k',k);%MEX
toc

tic
[idc,dist]=knnsearch(qp,p,k);%  VECTORIZED M-CODE
toc

p=rand(N,dim);
qp=rand(Nq,dim);

Output:

Elapsed time is 0.962640 seconds.
Elapsed time is 18.813100 seconds.

For info, questions, suggestions, bugs: giaccariluigi@msn.com

Download Now

VN:F [1.8.8_1072]
Rating: 0.0/10 (0 votes cast)
VN:F [1.8.8_1072]
Rating: +1 (from 1 vote)

Popularity: 7% [?]

Share and Enjoy:
  • Print
  • Digg
  • Sphinn
  • del.icio.us
  • Facebook
  • Mixx
  • Google Bookmarks
  • Blogplay
  • Live
  • PDF
  • Technorati
  • Twitter
  • Yahoo! Bookmarks
  • Add to favorites
  • email
  • MySpace
  • RSS

Related Posts

Tags: , , , , , ,

Comments

2 Comments on K-Nearest Neigbors and Radius (Range) Search

  1. Arne Bøckmann on Mon, 12th Oct 2009 18:29

    2. Could you provide an example on how to find the sparse connectivity matrix with a specified cut-off radius ? Could this radius also differ from point to point?

    [Reply]


    Luigi Giaccari Reply:
    October 12th, 2009 at 19:53

    Try this:

    N=1000;%number of reference points
Nq=10;%number of query points
dim=3;%dimension of points
r=.2;%Search radius
 
p=rand(N,dim);
qp=rand(Nq,dim);
 
A=sparse(N,N);%building the sparse matrix
 
for i=1:Nq
idc=BruteSearchMex(p',qp(i,:)','r',r);%%Radius Neighbor
m=length(idc);%number of neighbours found
A([i*ones(1,m),idc],[idc,i*ones(1,m)])=1;%add element to matrix
end

    Consider that sparse matrix in Maltab is class defined for doubles. So if you want a logical amtrix you need to use:

    A=false(N,N);

    It depends on what are your requirements.

    Second, yes radius can be different. Radisu search supports only one query time so you have to call the rourtine each loop.

    Good luck

    Luigi

    [Reply]

    UA:F [1.8.8_1072]
    Rating: 0.0/5 (0 votes cast)
    UA:F [1.8.8_1072]
    Rating: 0 (from 0 votes)

Tell me what you're thinking...
and oh, if you want a pic to show with your comment, go get a gravatar!


Include MATLAB code in your comment by doing the following:

<pre lang="MATLAB">

%insert code here

</pre>