How do I traverse a KDTree to find k nearest neighbors?

Question

This question concerns the implementation of KNN searching of KDTrees. Traversal of a KDTree to find a single best match (nearest neighbor) is straightforward, akin to a modified binary search.

How is the traversal modified to exhaustively and efficiently find k-best matches (KNN)?

Edit for clarification: After finding the nearest node M to the input query I, how does the traversal algorithm continue to find the remaining K-1 closest matches to the query? Is there a traversal pattern which guarantees that nodes are visited in order of best to worst match to the query?

Answer 1

You can maintain a max heap of size k (k is the count of nearest neighbors which we wanted to find).

Start from the root node and insert the distance value in the max heap node. Keep on searching in k-d tree using dimensional splitting , criteria and keep updating Max Heap tree.

https://gopalcdas.wordpress.com/2017/05/24/construction-of-k-d-tree-and-using-it-for-nearest-neighbour-search/

~Ashish