Fast restricted nearest neighbor search using KD Tres.

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.

Answer 1

[Vineet Joshi]

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.