Understanding How to Manually Code the KDTreeSearcher

6 次查看（过去 30 天）
Matpar
Matpar 2019-10-7
评论： Naveen Somasundaram 2022-1-18
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!
  1 个评论
Walter Roberson
Walter Roberson 2019-11-19
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（1 个）

Prabhan Purwar
Prabhan Purwar 2019-11-19
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:
  2 个评论
ZMC
ZMC 2020-10-15
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
Naveen Somasundaram 2022-1-18
Did you get an update on adding points to the kdtree searcher object?

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by