Search code examples
c++machine-learningkdtreeknn

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

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

Solution

  • 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).