kd-tree for matlab

A kd-tree mex lib which allows for nearest neighbor, k-nearest neighbor, range and ball queries

Description

kdtree provides a minimalistic implementation of kd-tree. The implementation can be used either inside MATLAB by means of MEX calls, or as a standalone tool, directly from a C/C++ program. The image on the website has been creaed with "fulltest.m"

This implementation offers the following functionalities:
- kdtree_build: k-d tree construction O( n log^2(n) )
- kdtree_delete: frees memory allocated by kdtree
- kdtree_nearest_neighbor: nearest neighbor query (for one or more points)
- kdtree_k_nearest_neighbors: kNN for a single query point
- kdtree_range_query: rectangular range query
- kdtree_ball_query: queries samples withing distance delta from a point

For more information, please refer to the following page:
https://sites.google.com/site/andreatagliasacchi/software/matlabkd-treelibrary

Acknowledgements

The author wishes to acknowledge the following in the creation of this submission:
k-D tree
This submission has inspired the following:
Kdtree implementation in matlab

• MATLAB release: MATLAB 7.6 (R2008a)
• Other requirements: Requires a working MEX compiler. Runs on all platforms.

[Gary Tam]

Thank you! Work out of the box.

[Luigi Giaccari]

The most complete Kd-tree on Matlab exchange.
 Thank you Andrea

[KIgor Karic]

For some reason kdtree_nearest_neighbor takes extremely long time to finish. Are others having the same problem or am I the only one?

[Andrea Tagliasacchi]

Thanks Kigor, I found a simple bug in the kdtree_nearest_neighbor data conversion. The query was executed MxN times instead of M times; given the query matrix Q is of size(M,N).

The updated kdtree_nearest_neighbor.cpp file can be found at
https://latis.cs.sfu.ca/svn/users/ata2/matlibs/kdtree/

The bug will be corrected in the next release

[Bing Jian]

How to use the result returned by kdtree_build()
which is a double number on my MATLAB7.5.0?
Does your program require at least MATLAB7.6?
Thanks!

[Andrea Tagliasacchi]

kdtree_build() returns a pointer to the kdtree. That number needs to be fed as first argument to every other query method. I haven't tried it on older versions of Matlab but I haven't used any of the new releases functionality.

[Florian Brucker]

Worked perfectly out of the box after compiling in MATLAB as specified by the docs. Thanks a lot!

One little thing: The help for kdtree_k_nearest_neighbors says that the neighbors are returned with increasing distance order. This seems to be incorrect, my experiments tell me they are returned in decreasing distance order (e.g. if the point itself is part of the tree, then it is returned as the last of the neighbors, not as the first).

[lin ming]

great work!
note: compile with visual c++ 6.0 will cause fatal error on my computer. However, VS2008 works fine.

[sun jin]

kdtree_build.cpp
D:\kdtree1.2\kdtree\KDTree.h(144) : error C2374: 'dIdx' : redefinition; multiple initialization
        D:\kdtree1.2\kdtree\KDTree.h(137) : see declaration of 'dIdx'
D:\kdtree1.2\kdtree\KDTree.h(225) : error C2371: 'i' : redefinition; different basic types
        D:\kdtree1.2\kdtree\KDTree.h(223) : see declaration of 'i'
 
  D:\MATLAB\R2008A\BIN\MEX.PL: Error: Compile of 'kdtree_build.cpp' failed.
 
??? Error using ==> mex at 207
Unable to complete successfully.

[Dominic]

Thanks a lot for this contribution - I've been using it a lot recently and it just works perfectly :)

[Dominic]

On my System (64bit Ubuntu, Matlab R2009a) there seems to be a memory leak with this implementation:

for i = 1:1000
tree = kdtree_build(rand(1000,1));
end

grabs around 140MB of system memory, according to top. That is never released again. Do I have to release the resources myself in some way or might this be a bug?
I really depend on this implementation, so you would do me a great favour by having a look at it...

[Dominic]

Ok, Shame on me, there is a method

"kdtree_delete"

that needs to be called for releasing the memory again.

[Alastair Harrison]

This is a really nice implementation. It's worked very well for me and is much faster than other implementations I've tried.

If I accidentally call kdtree_delete twice on the same handle, matlab quits immediately. Would it be possible for the library to maintain an internal list of handles to avoid this problem?

It would also allow implementation of a 'kdtree_delete_all' function, to free up all trees that have been created in a session. That's useful because if a piece of matlab code crashes before it gets to kdtree_delete then you can end up with an orphaned tree.

It would be nice to have a 'kdtree_delete_all' function to free up all trees that have been created. Of course, this would require a list of trees to be maintained within the library.

[Andrea Tagliasacchi]

The easiest solution would be enclosing the methods in a Matlab class and let Matlab call the "delete" functions automatically.

I might work on it in the future and improve it to include this functionality as well. I suggest you to be more careful with your de-allocations in the meantime :)

[Georgios Evangelidis]

Very nice and complete work! It worked perfectly. VC Express Ed. 2008 works fine. Thanks a lot!.

[Eval Bladimir Bacca Cortes]

It works really nice, but I need something and I don't know how to do it efficiently. I need to update an existing kd-tree with new data, but without losing the actual indexes. Is that possible? Please could you help me? Thanks in advance for your time....

[Andrea Tagliasacchi]

Hello Eval, that's a completely different problem, the underlying structure of this kd-tree is built to exploit the complete balancedness of the data. If you need a dynamic kd-tree then you would need to code it differently. By the way, why kd-tree? They are not exactly the best for this kind of task. Have you ever thought about using quad or octrees? Well, unless you have very high dimensional data...

[Duy Nguyen]

Hello Mr.Andrea Tagliasacchi, your code is really great but i need some other things. I wonder how i can make the function nearest neighborhood get distances between corresponding pairs. I mean that function's output return not only indexes but also the distances. Thank you in advance for your time

[Prateek Rungta]

Hi Andrea,
Thanks for the file, great work. Just a FYI: the tree doesn't appear to be correctly created in the event there are nan values in the data-set. In my tests, the points need to be at least 50-60% non-nan for the tree to work as expected.

[Jose]

Great work! I'm using it in my thesis project and it works well. But I don't know how I can delete nodes in the tree meanwhile keep the tree balanced.