The kd-tree is a well-known data structure, which alongside quadtrees and octrees, is commonly used for the task of space partitioning. That is, it aims to represent a set of points in k-dimensional space in a way that is efficient to access. Kd-trees, as do all binary trees, have the notable advantage of an average search time, far superior to the naive search.
While such trees perhaps have their best known application in computer graphics, I discovered them here in relation to a computational physics project on which I am currently working. For those who are curious about the context, I have recently been doing some statistical analysis on the distribution stars using the Hipparcos catalogue. Unfortunately due to sheer number of stars (100,000+), performing a nearest neighbour search or range search on each star in 3D (Euclidean) space is simply infeasible without the use of a clever algorithm. This is how I discovered the wonder of kd-trees, reducing a task that would otherwise take days to several minutes.
The software I am writing for this project happens to be in C# 4.0, and upon a bit of investigation, I discovered that there exists no (decent) implementation of the kd-tree structure and its algorithms for .NET. Thus, with a bit of help from the Wikipedia article and a paper I dug up, I decided to have a go at a generic implementation. Now that it is complete and tested, I can gladly declare that the job was not half as easy as I expected (but somehow quite rewarding)!
The following features have been implemented (and fully documented with XML comments).
- Tree construction
- Dynamic node addition
- Dynamic node removal
- Nearest neighbour search
- Range search
I’ve now uploaded the complete code for the implementation, which is available below as several C# code files. Note that you will also need the (wonderful) Math.NET Numerics library to compile things – it provides the generic vector type and a few other handy things. (You can probably adapt the code easily enough if you don’t fancy having this dependency.)
(All code is licensed under the MIT license. Copyright 2011 Alex Regueiro.)
Tests (MSTest framework)
The idea is that the KdTree class is available to use as a black box, so let me know if anything is unclear. (If you’re wondering though, the arithmetic stuff is there to provide generic arithmetic support complementing the generic vector support. You’ll probably just want to use double most of the time.) Finally, if you’re interested in the unit tests, you can grab them over at the project repository. Enjoy.