Fast restricted nearest neighbor search using KD Tres.

9 次查看（过去 30 天）
Samuel L. Polk
Samuel L. Polk 2021-3-19
回答： Vineet Joshi 2021-3-24
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,:)
end
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.

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

回答（1 个）

Vineet Joshi
Vineet Joshi 2021-3-24
Hi
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.

类别

在 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