Is it possible to find the KNN for a node that is *IN* the KD-tree?

Question

Trying to create a KNN search using a KD-tree. I can form the KD-tree fine (or at least, I believe I can!). My problem is that I am searching to find the closest 2 neighbours to every point in a list of points.

So, is there a method to find the K nearest neighbours to a point using a KD tree even if the point is actually IN the tree, or do I need to construct a seperate KD tree for each point, leaving out the point that I wish to search for?

My implementation language is C++, but I am more looking for either an algorithm or general help, thanks!

Thanks, Stephen

Answer 1

If you want the K exact nearest-neighbors within your tree, just query the tree for K+1 neighbors (obviously since the first nearest neighbor will be your query).

Answer 2

This isn't really much of an answer, but I can't fit what I want to paste into a comment. Anyhow, here's the relevant text from Wikipedia:

The algorithm can be extended in several ways by simple modifications. It can provide the k-Nearest Neighbors to a point by maintaining k current bests instead of just one. Branches are only eliminated when they can't have points closer than any of the k current bests.

It can also be converted to an approximation algorithm to run faster. For example, approximate nearest neighbour searching can be achieved by simply setting an upper bound on the number points to examine in the tree, or by interrupting the search process based upon a real time clock (which may be more appropriate in hardware implementations). Nearest neighbour for points that are in the tree already can be achieved by not updating the refinement for nodes that give zero distance as the result, this has the downside of discarding points that are not unique, but are co-located with the original search point.

Approximate nearest neighbor is useful in real time applications such as robotics due to the significant speed increase gained by not searching for the best point exhaustively. One of its implementations is Best Bin First.

Answer 3

I'd recommend taking a look at ANN for implementation details http://www.cs.umd.edu/~mount/ANN/

It's designed for approximate nearest neighbor searches, but can also do exact nearest neighbor searches. It's also some of the clearest and best written code I've ever found, and should give you some insight even if you want your own implementation.