Ultra-fast Nearest neighbor search

Builds a nearest neighbor graph in a very short time.In many cases is faster than ANN library.

Description

In this file you can find a simple but effective algorithm for NN Search which I megalomaniacly called the GLTree.  
 
 
It has been designed for uniformly random data but works fine even on sparse ones. If point are too sparse, for example logspace data, search is still performed correctly but speed can degenerate to a brute serch algorithm. In these cases a different data structure is needed but for lack of time and C++ skill I havent' still coded. It only supports 2D points.  
 
This new release includes:  
 
-NNSearch  
-KNNSearch  
-RadiusSearch  
 
Moreover diferrently from the last version now the tree can be build without running any search. The pointer passed to workspace can be used for the above routines.(Thanks to Andrea Tagliasacchi for his precious tips).  
It is possible to choose if return the distances.  
 
3D version wont be ready for a while.  
 
Some of this functions are brand new so please advise me if any error occurs.  
 
I AM LOOKING FOR C++ DEVELOPPERS WHO WANTS TO JOIN THE PROJECT TO ENLARGE AND MAKE MORE EFFICIENT THIS UTILTY. CONTACT ME IF YOU ARE INTERESTED.  
 
I want to tell you that i am a C++ beginner, the code may look inefficient or childish to you, so if you have suggestions,  
especially about the code metric, data structure or bottlenecks etc, it will be greatly appreciated.  
Even things that may seem stupid to you wont seem to me.  
 
 
Here is an example :  
 
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=BuildGLTree(px,py);  
NNG=NNSearch(px,py,qx,qy,ptrtree);  
toc  
 
tic  
NNG= annquery([px,py]',[qpx,qpy]', 1);  
toc  
 
Output:  
 
1.46715 s  
6.13951 s  
 
 
 
If any problems occurs in execution, or if you found a bug, have a suggestion or question just contact me at:  
 
[e-mail]

• MATLAB release: MATLAB 7.5 (R2007b)
• Other requirements: Need a mex compiler

Other Files

GLTree020109/NNSearch.m,
GLTree020109/NNSearch.cpp,
GLTree020109/KNNSearch.m,
GLTree020109/,
GLTree020109/TestMexFiles.m,
GLTree020109/KNNSearch.cpp,
GLTree020109/GLTree.cpp,
GLTree020109/RSearch.m,
GLTree020109/RSearch.cpp,
GLTree020109/BuildGLTree.m,
GLTree020109/ReadMe.m,
GLTree020109/BuildGLTree.cpp,
GLTree020109/GLTree.h

[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.