Understanding How to Manually Code the KDTreeSearcher

Hi Professionals, it me again and again!

From my previous trials and fails, I understood the process of manually coding how the Exhaustive Search Operates in the Knn algorithm.

Please correct me if I am wrong, this process takes the all/ nearest neighbor points measures their distances (euclidean,manhatt.etc..)and apply a sort feature to get the closest distance, smallest distance or least distance value.

Now I am trying to understand how this works for the KDTsearcher can a professional guide me please? I have no code, just the will to understand be googling as well.

There are loads of professionals that responde to my rediculous questions trying to interpret my insane chaotic methods, for this I thank you immensely for acknowleding me!

Sincerly thank you's, I am really trying to get this and with your aid I feel a tad more confident to try! One day I will be proficient but it may not be today! Thanx a mill!

[Walter Roberson]

The KDTsearcher is related to Octree encoding, https://en.wikipedia.org/wiki/Octree . A pre-pass is done that orders the data in two dimensions in a relatively simple way, and once that is done, it is a lot faster to search the data. It is the multidimensional equivalent of sorting first and then doing a binary search.

Answer 1

[Prabhan Purwar]

Hi,

The nearest neighbour search (NN) algorithm aims to find the point in the tree that is nearest to a given input point. This search can be done efficiently by using the tree properties to quickly eliminate large portions of the search space.

Searching for a nearest neighbour in a k-d tree proceeds as follows:

1. Starting with the root node, the algorithm moves down the tree recursively, in the same way that it would if the search point were being inserted (i.e. it goes left or right depending on whether the point is lesser than or greater than the current node in the split dimension).
2. Once the algorithm reaches a node, it checks that node point and if the distance is better, that node point is saved as the "current best".
3. The algorithm unwinds the recursion of the tree, performing the following steps at each node:

1. If the current node is closer than the current best, then it becomes the current best.
2. The algorithm checks whether there could be any points on the other side of the splitting plane that are closer to the search point than the current best. In concept, this is done by intersecting the splitting hyperplane with a hypersphere around the search point that has a radius equal to the current nearest distance. Since the hyperplanes are all axis-aligned this is implemented as a simple comparison to see whether the distance between the splitting coordinate of the search point and current node is lesser than the distance (overall coordinates) from the search point to the current best.

• If the hypersphere crosses the plane, there could be nearer points on the other side of the plane, so the algorithm must move down the other branch of the tree from the current node looking for closer points, following the same recursive process as the entire search.

• If the hypersphere doesn't intersect the splitting plane, then the algorithm continues walking up the tree, and the entire branch on the other side of that node is eliminated.

4. When the algorithm finishes this process for the root node, then the search is complete.

The algorithm uses squared distances for comparison to avoid computing square roots.

Refer to the following link for further information:

• https://www.mathworks.com/help/stats/kdtreesearcher.html(KDTreeSearch)

[ZMC]

Hi Prabhan,

I would like to know is it possible to dynamically add tree node to the kdtree in Matlab? I am gathering data gradually and want to maintain a kdtree rather than rebuild a new kdtree each time when a new data arrives.

But in the kdtresearcher manual, I didn't find a way to do it.

Thanks for any advice!

[Naveen Somasundaram]

Did you get an update on adding points to the kdtree searcher object?