GLTree:Fast K-Nearest Neighbors Search

August 25, 2009 by Luigi Giaccari 
Filed under: Algorithms, Computational Geometry 
8 Comments
VN:F [1.8.8_1072]
Rating: +2 (from 2 votes)
VN:F [1.8.8_1072]
Rating: 10.0/10 (5 votes cast)

In this file you can find a simple but very effective algorithm for Nearest Neighbour Search which I megalomaniacly called the GLTree.

You want more? go to the Professional version of GLTree

It has been designed for uniformly random data, where is the fastest I ever used, but works fine even on sparse ones. If points are too sparse, for example logspace data, search is still performed correctly but speed can degenerate to a brute search algorithm. In these cases a different data structure is needed but for lack of time I haven’t still coded. If query points are close to reference it is very efficient on sparse dataset too.

The tree can be build without running any search. The pointer passed to workspace can be used for the above routines. The tree costruction has linear time complexity and it is very fast, so it becomes advantageus against brute search even for a small number of points. I’d like to point that in GL-Tree searching has linear complexity (on uniform dataset) instead of n*log(n) like in kd-tree.
It is possible to choose if return the distances.

This release includes:

  • NNSearch

It only supports 2D points and 3D points.

It also possible to ask for personalized versions like:

  • different points data structure or class. To use the utility as C++ library.
  • Detections of sparse dataset. (sparse dataset are detected very soon so it is convenient to switch to a kd-tree data structure).
  • More efficient in terms of memory and speed costruction of the tree.
  • Personilzed functions, NNgraph, box search…
  • user’s suggestions
  • explanations on how the algorithm works

Some of this functions are brand new so please advise me if any error occurs.

Here is an example on 2D, find 1e6 neighbours in 1e6 reference:

N=1000000;
%random reference and query points
px=rand(N,1);%reference
py=rand(N,1);
qpx=rand(N,1);%query
qpy=rand(N,1);

tic
ptrtree=BuildGLTree2DFEX(px,py);
NNG=NNSearch2DFEX(px,py,qx,qy,ptrtree);
toc

Output:

1.46715 s


And here are the timings for 3D version:

  • N=100; elapsed time is: 0,001 seconds
  • N=1000; elapsed time is: 0,003 seconds
  • N=10000; elapsed time is: 0,029 seconds
  • N=100000; elapsed time is: 0,325 seconds
  • N=1000000; elapsed time is: 3,346 seconds

If any problems occurs in execution, or if you found a bug, have a suggestion or question just contact me at:

giaccariluigi@msn.com

This work is free thanks to users gratitude. If you find it usefull consider making a donation.

Downloads:
You want more? go to the Professional version of GLTree
VN:F [1.8.8_1072]
Rating: 10.0/10 (5 votes cast)
VN:F [1.8.8_1072]
Rating: +2 (from 2 votes)
GLTree:Fast K-Nearest Neighbors Search10.0105

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

8 Comments on GLTree:Fast K-Nearest Neighbors Search

  1. Andrew on Tue, 3rd Nov 2009 22:42

    2. When I run mex DeleteGLTree.cpp on version R2009a with Mac OS 10.6 (Snow Leopard), I get the following message:

    Undefined symbols:
    “_mexFunction”, referenced from:
    -exported_symbols_list command line option
    ld: symbol(s) not found
    collect2: ld returned 1 exit status

    mex: link of ‘ “DeleteGLTree.mexmaci”‘ failed.

    This turns out to be a problem with the declaration of mexFunction. For the solution, see
    http://www.mathworks.co.kr/matlabcentral/newsreader/view_thread/173095

    [Reply]


    Luigi Giaccari Reply:
    November 3rd, 2009 at 22:44

    Thank you for your report, it will be fixed in the next release.

    [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)
  2. Tobias on Thu, 3rd Dec 2009 09:34

    3. Hi

    I’ve been using this code under windows but I also would like it to work under Linux. At first the TestMexFiles stopped right away and complained about this line in KNNSearch.cpp:
    #include “GLtree.cpp”
    where I changed the lower case t to a T.
    But there seems to be something else wrong with the DeleteGLTree. This is what happens when I run TestMexFiles now:
    …

    DELETING THE TREE
 
Mex file entry point is missing. Please check the (case-sensitive) 
spelling of mexFunction (for C MEX-files), or the (case-insensitive) 
spelling of MEXFUNCTION (for FORTRAN MEX-files). 
??? Invalid MEX-file 
'/home/tfy05/tfy05thd/edu/Optronic/Matlabkod/GLTree230909/DeleteGLTree.mexglx': .
 
Error in ==> TestMexFiles at 75 
DeleteGLTree(ptrtree);"

    Do you know what the problem is?

    /Tobias

    [Reply]


    Luigi Giaccari Reply:
    December 3rd, 2009 at 11:17

    I am sorry but I am very busy this days.

    I hope I can fix this problem in the next release which is scheduled for early 2010.

    I don’t have a MAC nor a Linux system but I thing I know what the problem is.

    Thank you

    [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)
  3. John Kua on Mon, 8th Mar 2010 23:07

    4. When will k-NN search and radius search be put back into the distribution? Thanks!

    [Reply]

    UN:F [1.8.8_1072]
    Rating: 0.0/5 (0 votes cast)
    UN:F [1.8.8_1072]
    Rating: 0 (from 0 votes)
  4. Luigi Giaccari on Tue, 9th Mar 2010 08:54

    5. A new more efficient version of the KNN and radius search can be found here.

    Understood the potential of this library, I decided to give it for a symbolic price in order to have support to enlarge it.

    [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)
  5. fakaza on Fri, 23rd Apr 2010 12:31

    6. hi
    I want to run KNN on windows vista and by Dev C++ 4.9.9.2
    but it doesn’t run
    what shoud I do?
    shouldn’t it want from me an input?
    I have a text file which contains points coordinate.
    Is this an input or the input is something else?
    whould you please send me something which describe the KNN algorithm?
    maybe I have not understood it rightly?
    thanks
    bye

    [Reply]

    UN:F [1.8.8_1072]
    Rating: 0.0/5 (0 votes cast)
    UN:F [1.8.8_1072]
    Rating: 0 (from 0 votes)
  6. Andrew on Fri, 9th Jul 2010 05:15

    7. @Tobias: You can fix this error by removing the erroneous “const” modifier from the second argument to “mexFunction”

    [Reply]

    UN:F [1.8.8_1072]
    Rating: 0.0/5 (0 votes cast)
    UN: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>