FAST K-NEAREST NEIGHBORS SEARCH

Simple but very fast algorithm for nearest neighbors search in 2D space.

Description

You can find the description at:

http://www.advancedmcode.org/gltree.html

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
K-NEAREST NEIGHBOURS AND RADIUS (RANGE) SEARCH
This submission has inspired the following:
K-NEAREST NEIGHBOURS AND RADIUS (RANGE) SEARCH, FAST K-NEAREST NEIGHBOURS SEARCH 3D VERSION

• MATLAB release: MATLAB 7.5 (R2007b)
• Other requirements: Need a mex compiler
• Other Files: BuildGLTree2DFEX.cpp, ; BuildGLTree2DFEX.m, ; DeleteGLTree2DFEX.cpp, ; DeleteGLTree2DFEX.m, ; GLTree2DFEX.cpp, ; GLTree2DFEX.h, ; license.txt, ; NNSearch2DFEX.cpp, ; NNSearch2DFEX.m, ; TestMexFiles.m

[matt dash]

I get an error when running "mex GlTreeMex.cpp" with
"Lcc-win32 C 2.4.1 in C:\PROGRA~1\MATLAB\R2007b\sys\lcc"
as my compiler.

[Luigi Giaccari]

I don't know what can it be, I used Visual c++ 6.0,
  if you want an already compiled win32 mex you can contact me on my e-mail (Matlab exchange stuff do not axcept any more mex files, I can even send you the whole test with ann library).

I am sorry, with other files I have had this mex problem too.

[a]

1) using the data provided in the demo file, ANN library took 0.02 seconds; this code took 0.06 seconds; for N=1e7, this code was 10 times slower than ANN library. Please be more specific when saying "In many cases is faster than ANN library". Also, ANN supports more options (arbitrary dimensions, etc).
2) to make it compile, I had to fix the following:
a) replace the mexFunction line in GLtreeMex.cpp by:
void mexFunction( int nlhs, mxArray *plhs[],int nrhs, const mxArray *prhs[]){
b) replace mex GlTreeMex.cpp with mex GLtreeMex.cpp
c) replace NNG=GLTreeMex(px,py,qpx,qpy); by:
NNG=GLtreeMex(px,py,qpx,qpy);

[Luigi Giaccari]

1)I don't Know what kind of data you used but I didn't provide any.
The demo file contains just random points generation.
My pc do not support 1e7 due to help memory error, anyway finding the NNG in 1e7 points take much longer than 0.02 sec for both algorithoms.
My algorithom suffers query points outside the bounding box of reference, this should be the case in which ANN is faster.
2)One thing you are right is that ANN is more flexible.
3)From your comment it is not clear what you changed seems just like you copied and pasted the same line.
4)you could at least use your name
5)If you have problems my e-mail is the best place where fix them so please avoid fake comments

[a]

1) Great code, works as advertised ! I would correct my initial rating to 5 stars if mathworks allowed that (there was probably a bug in my previous timing)
the speedup over ann library is quite impressive, for 2d inputs and k=1 nearest neighbor. For N=1e7, it ran in 20 sec instead of 80 for ann)

2) the changes I had to do to run the code are for compatibility with non-windows systems:
void mexFunction( int nlhs, const mxArray *plhs[1],
                  int nrhs, const mxArray *prhs[4])
changed to:
void mexFunction( int nlhs, mxArray *plhs[],int nrhs, const mxArray *prhs[])
(note the prhs[4], etc)

and case-sensitivity:
mex GlTreeMex.cpp => mex GLtreeMex.cpp
NNG=GLTreeMex(px,py,qpx,qpy); =>
NNG=GLtreeMex(px,py,qpx,qpy);
(note the case difference)

[Michael Jordan]

Excellent code. I am looking forward to your extension to 3D, k-neighbour and range search, which are more useful functions than the current one.

[James Tursa]

To Matt Dash: lcc is a C compiler, not a C++ compiler, so you should not expect lcc to compile cpp files.

[Johannes Korsawe]

Really good! Great work and just came in handy.
Thanks a lot for sharing your work!

[Bruno Luong]

Impressive running speed. I have tested against Matlab Delaunay/dsearch nearest point for 2 x 10^5 points and the code won hand down in speed. Very good work. I would like to see the author to provide mean/worse complexity of his algorithm, which is always necessary step when integrating in reliable software project.

[Luigi Giaccari]

Given:
 
 N=reference +query points

Complexity of the algorithm is linear for random uniformly spaced points. Both for the serach and the tree construction.

 It becomes N^2 (Brute search) for very sparse dataset.

However this patological case can be detected after 5-10% running time. In this case is better to switch to kd-tree data structure. ( this detection is not present in this version)

                    Luigi

[Andrew]

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

[Luigi Giaccari]

Thank you it will fixed in the next release.
Please report comments on :
http://www.advancedmcode.org/
I don't check my FEX profile very often.

Thank you again

 Luigi

[Tobias]

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 it now:

COMPILING:

Warning: You are using gcc version "4.3.2-1.1)". The earliest gcc version supported
         with mex is "4.0.0". The latest version tested for use with mex is "4.2.0".
         To download a different version of gcc, visit http://gcc.gnu.org

BuildGLTree : mex succesfully completed.

Warning: You are using gcc version "4.3.2-1.1)". The earliest gcc version supported
         with mex is "4.0.0". The latest version tested for use with mex is "4.2.0".
         To download a different version of gcc, visit http://gcc.gnu.org

NNSearch : mex succesfully completed.

Warning: You are using gcc version "4.3.2-1.1)". The earliest gcc version supported
         with mex is "4.0.0". The latest version tested for use with mex is "4.2.0".
         To download a different version of gcc, visit http://gcc.gnu.org

KNNSearch : mex succesfully completed.

Warning: You are using gcc version "4.3.2-1.1)". The earliest gcc version supported
         with mex is "4.0.0". The latest version tested for use with mex is "4.2.0".
         To download a different version of gcc, visit http://gcc.gnu.org

RSearch : mex succesfully completed.

Warning: You are using gcc version "4.3.2-1.1)". The earliest gcc version supported
         with mex is "4.0.0". The latest version tested for use with mex is "4.2.0".
         To download a different version of gcc, visit http://gcc.gnu.org

DeleteGLTree : mex succesfully completed.

RANDOM POINTS GENERATED

BUILDING THE DATA STRUCTURE:
GLTree built in 0.0049 s
returned pointer 170460176:

START NEAREST NEIGHBOR SEARCH:
NNsearch of 1000 reference points and 100000 query points took: 0.0523 s

START K NEAREST NEIGHBOR SEARCH:
NNsearch of 3 neighbors in 1000 reference points and 100000 query points took: 0.1780 s

START RADIUS SEARCH:
Rsearch of 1000 reference points and 100000 query points
within a radius of 0.0100 took: 3.3849 s

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);

[vortse a]

Why did you remove KNN and Radius search?

[Luigi Giaccari]

A new version, faster and less memory hungry will be available shortly.