MATLAB Answers

Fast restricted nearest neighbor search using KD Tres.

6 views (last 30 days)
Samuel L. Polk
Samuel L. Polk on 19 Mar 2021
Answered: Vineet Joshi on 24 Mar 2021
I would like to implement a restricted nearest neighbor search for each point in a data matrix X. Specifically, I would like to find the nearest neighbor of X(i,:) among the rows of X(mask_i,:), where mask_i is a logical mask depending on X(i,:).
Below is a brute force way of accomplishing this task, using the KDTreeSearcher model. In it, I store the index of X(i,:) to its nearest neighbor in X(mask_i,:) in an array r.
for i=1:n
Mdl = KDTreeSearcher(X(mask_i,:)); # Build KD tree on subset of X satisfying mask_i
r[i] = knnsearch(Mdl, X(i,:)); # Nearest neighbor of X(i,:) in X(mask_i,:)
However, this approach is very computationally expensive since it requires training a new KD-Tree for each query. My question is whether there is a way to train a Kd-tree once (before the for-loop) and query the Kd-tree for nearest neighbors among data points in X(mask_i).
If Kd-trees aren't the right tool for this sort of problem, I would appreciate any suggestions for the right one. Thank you very much.

Answers (1)

Vineet Joshi
Vineet Joshi on 24 Mar 2021
The kdtreesearcher’s data property is by default read only and cannot be changed and thus it won’t allow you to resample the data after being created.
To reduce the time complexity, you can start by setting the ‘SortIndices’ value to false in knnsearch, this will reduce the overhead of sorting the neighbors.
Another way to accelerate the entire process is to parallelize the search. The Parallel Computing Toolbox provides capabilities to run knnsearch on GPU. Kindly refer to the following documentation for reference : Run MATLAB Functions on a GPU.
Note on GPU knnsearch will use exhaustive method to find the neighbors as kdtrees are inherently serial in in nature.
Hope this helps.

Community Treasure Hunt

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

Start Hunting!