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. Bjoern Heckel added the ability to return multiple nearest neighbors, instead of just one. Michael Lorton 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.

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)