CODEWITHSUNDEEP
algorithmtree
ArafatK
ArafatK

Reputation: 760

How to efficiently find k nearest neighbours from a kd tree

Actually the question has been asked before but to the best of my knowledge no appropriate answers have been provided.

I understand how to implement k-d tree and how the nearest neighbor search for it works. However even after looking around, I can't find an efficient way to search for k nearest neighbors very efficiently using k-d tree. I can only think of finding the nearest neighbor and deleting it and repeating the process again k-1 times and then inserting all the deleted nodes back into the tree. But that seems redundant and totally beats the purpose.

I just want to find a simple way to find the k nearest neighbors using k-d tree. I am not looking for an online implementation or a library which could let me do that. I just want to understand the logic and then I will implement it myself.

Upvotes: 4

Views: 2726

Answers (1)

mcdowella
mcdowella

Reputation: 19601

The algorithm at https://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search can be regarded as an optimisation of "search the whole tree recursively" and the optimisation is to work out when the subtree you are about to search cannot possibly contain an improvement on the current best neighbour.

To change this to find the k nearest neighbours, keep k nodes found so far instead of just one closest node, and keep track of the distance to the furthest of these nodes. Then decide to search a subtree, or ignore it, based on whether the closest point within that subtree can possibly be an improvement on the furthest one of these k neighbours.

You will want a data-structure, such as a heap, which allows you to keep k items, find the item with the highest value of distance, remove that item, and insert a newly found item.

Upvotes: 5

Related Questions