Tutorial: Nearest Neighbor Search

This page demonstrates how to create KDTree from a data set and use it for a nearest neighbor search. To construct a KDTree we need a dataset, a specified number of dimensions and a metric function.

Obtain a Dataset

For this example, we will generate a 2-dimensional dataset of type double. Here is a simple function to generate some data

public static double[][] GenerateData(int points, double range)
{
	var data = new List<double[]>();
	var random = new Random();

	for (int i = 0; i < points; i++)
	{
		data.Add(new double[] { (random.NextDouble() * range), (random.NextDouble() * range) });
	}

	return data.ToArray();
}

Define a Metric

We will choose the standard euclidean distance as our metric function.

Func<double[], double[], double> L2Norm = (x, y) =>
{
	double dist = 0;
	for (int i = 0; i < x.Length; i++)
	{
		dist += (x[i] - y[i]) * (x[i] - y[i]);
	}

	return dist;
};

One thing to note here about the metric function; It does not have Math.Sqrt() or Math.Pow(). This is because the metric function will be called many times. You should make this as lightweight as possible. The overhead of calling a function makes a difference when called a few million times.

Construct a KDTree

Lets generate 1,000,000 points and 10,000 test points to perform nearest neighbor searches against. Once we have this data, we simply provide the data to the KDTree constructor. Since this is a test and we don't have any true objects to associate with our points, we will just provide the ToString() of each point as a node object.

var treeData = GenerateData(1000000, 1000);
var treeNodes = treeData.Select(p => p.ToString()).ToArray();
var testData = GenerateData(10000, 1000);
var tree = new KDTree<double, string>(2, treeData, treeNodes, L2Norm);

Nearest Neighbor Searching

To do a nearest neighbor search of any point we simply call the NearestNeighbors method on the tree and give it a test point and the desired number neighbors to find. For the example, lets do this on each point in out test data. Even better; lets time it using the StopWatch class.

var stopwatch = new Stopwatch();
stopwatch.Start();
for (int i = 0; i < testData.Length; i++)
{
	var test = tree.NearestNeighbors(testData[i], 3);
}
stopwatch.Stop();

Console.WriteLine("Milliseconds: " + stopwatch.ElapsedMilliseconds);
Console.Read();

The results I obtain on my machine:

Milliseconds: 120

10,000 3-neighbor searches on 1,000,000 2-dimensional points in 120 milliseconds. Not bad!