KD-Tree Implementation in Java and C#
A KD-tree is a data structure for efficient search and nearest-neighbor(s) computation of points in K-dimensional space. I like programming in Java and couldn’t find any Java KD-tree implementations on the Web, so I wrote this one. (There appear to be better implementations now, like the ones mentioned on this site.) I also thank the following contributors:
- Eric Burnett, who patched a memory leak and suggested an improvement for memory allocation.
- Andrey Fomin, who has provided a Polish translation of this page.
- Bjoern Heckel, who added the ability to return multiple nearest neighbors, instead of just one.
- Robbie Hott, who fixed a bug in the KDNode.edit() method and added a JUnit test in KDTests.java to check a simple example.
- Michael Lorton, who added unit tests, changed the interface to use generics and modern container classes, and made the code thread-safe (though as with all aspects of software, we make no guarantees). If you want to use the unit tests, you will have to obtain the junit package from Sourceforge. Michael is now using KDTree to help match people on his SpeedDate website.
- Zhiheng Xu, who made the core classes serializable.
The file kd.jar contains the Java class edu.wlu.cs.levy.CG.KDTree, which supports the standard KD-tree operations insert, delete, equality search, range search, and nearest-neighbor. There is also a version for C#, written by Marco A Alvarez, in KDTreeDLL.zip.
The JAR file contains the class files of course, but also all the source and the Makefile, for anyone wishing to hack the code (KDTree.nearest could probably be improved). The demonstration programs kddemo, kdtime, kdrange, and kdnbrs show you how to use the KDTree class. To run these programs, do the following in Unix (or the equivalent Java commands on your platform):
% javac -classpath .:kd.jar kddemo.java % javac -classpath .:kd.jar kdrange.java % javac -classpath .:kd.jar kdtime.java % javac -classpath .:kd.jar kdnbrs.java % java -classpath .:kd.jar kddemo % java -classpath .:kd.jar kdrange % java -classpath .:kd.jar kdtime 10000 2 100 (for example) % java -classpath .:kd.jar kdnbrs 10000 3 100 (for example)