Get from Ico-github-logo

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from

  • kdtree_compile()
  • KDTree
    KDTree class
  • kdtree_delete_demo.m
    KDTREE_BUILD_DEMO: illustrate the functionalities of kdtree_delete
  • kdtree_load.m
    KDTREE_LOAD loads a kd-tree from a binary file
  • kdtree_ball_query.m
    KDTREE_BALL_QUERY query a kd-tree with a ball
  • kdtree_ball_query_demo.m
  • kdtree_build.m
  • kdtree_build_demo.m
    KDTREE_BUILD_DEMO: performances achieved by the preprocessing
  • kdtree_print.m
    KDTREE_PRINT prints the structure of a kd-tree
  • kdtree_delete.m
    KDTREE_BUILD destruct a kd-tree
  • kdtree_save.m
    KDTREE_SAVE saves a kd-tree to a binary file
  • KDTree_demo.m
    Input data
  • kdtree_figure_demo.m
  • kdtree_k_nearest_neighbors.m
  • kdtree_k_nearest_neighbor...
    clc, clear, close all
  • kdtree_k_nearest_neighbor...
  • kdtree_nearest_neighbor.m
    KDTREE_NEAREST_NEIGHBOR query a kd-tree for nearest neighbor
  • kdtree_nearest_neighbor_d...
    create data and execute query
  • kdtree_range_query.m
    KDTREE_RANGE_QUERY query a kd-tree with a range
  • kdtree_range_query_demo.m
    create data and query
  • View all files

Join the 15-year community celebration.

Play games and win prizes!

» Learn more

4.9 | 18 ratings Rate this file 44 Downloads (last 30 days) File Size: 715 KB File ID: #21512 Version: 1.4
image thumbnail




22 Sep 2008 (Updated )

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

| Watch this File

File Information

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
IMPORTANT NOTE: as Matlab offers a kdtree I have lost interest in maintaining this code.


This file inspired Kdtree Implementation In Matlab.

MATLAB release MATLAB 7.6 (R2008a)
Other requirements Requires a working MEX compiler. Runs on all platforms.
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (44)
14 Aug 2016 Andrea Tagliasacchi

Hello everybody, I just want to be clear about why I have stopped supporting this library.

I know many have reported my code is much faster than what is natively offered, but I have simply lost faith in mathworks.

I have been told by many this was the de-facto standard kdtree used by many researchers, and the fact that they released their own version without even giving out a simple token of acknowledgement was not very pleasant.

You should go ahead and use what they offer:

Have a great day

Comment only
05 Aug 2015 Matlab Learner

please give me sample input for this

Comment only
01 Jul 2015 vivek

vivek (view profile)

Can i use the KD tree to find intersections in N rectangles and compute the overlap area.Any idea will be regrettably appreciated.

Comment only
30 Jun 2015 Ehsan golk

I found that the data must be double to work properly, if you get "Matlab System Error", cast it.

29 Jun 2015 Ehsan golk

it is working fine with random data and examples but i dont know why it is not working in my data i have 279936x3 data. I even made a t = rand(279936,3); and its working but i dont know why ist not working on my data. i get "Matlab System Error" in kdtree_build(mydata);

Comment only
29 Jun 2015 Ehsan golk  
30 Mar 2015 Ralf

Ralf (view profile)

Note, there is a newer version.

Comment only
08 Dec 2014 Kobye

Kobye (view profile)

Extremely efficient, works great. Rare crashes as previously reported but not at a problematic interval.

26 Aug 2014 Thien Tran

I have same problem mentioned by Jon. I am using R2014a.

Any help, pls

Comment only
18 Aug 2014 Jon

Jon (view profile)

I am experiencing apparently random crashes from the query files in this package. The files compile just fine, but they don't always work.

I randomly get a "Matlab System Error" containing details indicating a segmentation violation on both R2012a and R2013a (Windows 64 bit). My compiler is Visual Studio 10.0

I am employing the kdtree_ball_query within a loop, where every point in the domain is checked. The points in the domain are shifted then checked again. On R2012a, the crash occurs after the same number of point-shifts (making me think it had something to do with the input data), but in R2013a, it crashes immediately.

I have tried the different query functions all with the same result. The kdtree_build function has never caused a crash. I don't know why this is happening, but it's too bad because otherwise this suite of files would be immensely useful!

Comment only
01 May 2014 Antonio

Hi, thanks for sharing the code.

I found a strange behavior from the computational execution time:


is far way faster than:


being P a point with 25 dimensions.

16 Jan 2014 Christos  
28 Oct 2013 BESMA

BESMA (view profile)

I tried to execute this code but i didn't undrestand the steps to do this!! ireally need it any help and thank you.

Comment only
07 Oct 2013 tarek zougari

great work & thx another time Andrea

am posting this for newbies next readers

1) install a compiler (u have to respect the order ) see here :

2) u have to be in matlab on the folder where the files are, see here :


04 Oct 2013 Andrea Tagliasacchi

Tarek, that just means you haven't compiled the library. @see kdtree_build

Comment only
04 Oct 2013 tarek zougari

Gracie mille Andrea for answering :)
i tried : mex kdtree_build.cpp

the msg i have is :

mex kdtree_build.ccp

" C:\PROGRA~1\MATLAB~1\R2013A\BIN\MEX.PL: Error: 'kdtree_build.ccp' not found.

Error using mex (line 206)
Unable to complete successfully."

ps : i did set the path

Comment only
14 Sep 2013 Eran

Eran (view profile)

One thing that is very important and missing is a way to save and load the tree to/from disk.
It takes ~1000s to generate a tree for
a 10^6 X 3 matrix. It will be useful if you can do it only once and load it from
hard drive in a fraction of a second.

15 Jun 2013 Lingji Chen

Great work! Thank you!

A question: I inferred this from your demo, but wanted to confirm with you: The index returned by a query is guaranteed to correspond to the row index of the data used to create the kd-tree, correct?

Comment only
22 Mar 2013 Philip Du Toit

Thank you! Gave my application 100x speedup.

07 Aug 2012 kenza

kenza (view profile)

hi every body
it's the first time who i participate in this blog, I am a beginner in matlab programmation. Actually, I try understand the K-d tree code. So i found a matlab sript for the implementing of algorithm. I give you the link to consult the sript code. My question is connected to the input of kdree code especially 'val'. What mean 'val' ? is it a matrix or array and how can i obtain it or calculate it?
I need your help. your answers can give me another reflexion.

15 Jun 2012 Andrea Tagliasacchi

Sorry for the butchered english in my last message ^_^

Comment only
14 Jun 2012 Andrea Tagliasacchi

Be advised.. The library has been subject to large updates and it's in Beta. It's much faster and it offers a matlab class wrapper. The updated library can be found at the following URL:
(Includes 64bit binaries for OSX and WIN7)

Comment only
04 Jun 2012 Andrea Tagliasacchi

@Jose, yah the tree is static.. sorry
@Bryan, that's a good question :) I am working on the library these days, I will try to answer it.

Comment only
04 Jun 2012 Bryan

Bryan (view profile)

Great work! Performance Question: Why is kdtree_nearest_neighbor() slower than kdtree_k_nearest_neighbors(...,1)? In my testing with the same set of 2000 4-dimensional points, k_nearest is 4x faster.

10 Jan 2012 Jose

Jose (view profile)

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.

21 Jun 2011 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.

17 Apr 2011 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

Comment only
21 Apr 2010 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...

Comment only
20 Apr 2010 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....

Comment only
15 Apr 2010 Georgios Evangelidis

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

10 Feb 2010 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 :)

Comment only
10 Feb 2010 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.

Comment only
26 Oct 2009 Dominic

Ok, Shame on me, there is a method


that needs to be called for releasing the memory again.

Comment only
22 Oct 2009 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));

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

Comment only
15 Oct 2009 Dominic

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

09 Sep 2009 sun jin

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.

Comment only
27 Aug 2009 lin ming

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

17 May 2009 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).

30 Mar 2009 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.

Comment only
07 Feb 2009 Bing Jian

Bing Jian (view profile)

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?

Comment only
03 Feb 2009 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

The bug will be corrected in the next release

Comment only
21 Jan 2009 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?

Comment only
03 Dec 2008 Luigi Giaccari

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

30 Sep 2008 Gary Tam

Thank you! Work out of the box.

12 Nov 2008 1.1

Corrected few bugs in parameter passing
Greatly enhanced the preprocessing speed (tree construction) 10x
Improved examples and makefile structure.
More info in "CHANGES"

08 Dec 2008 1.3

Updates some interface bugs and the bugs on distances (second argument) returned by the query functions.

01 Sep 2010 1.4

Redirected documentation to my personal page

06 Aug 2015 1.4

updated link to git repository (google code dead)

14 Aug 2016 1.4

linked to github repo

Contact us