Inferior performance of the kd-tree for K-NN point cloud neighbor searches

Hi,

I am currently trying to assess the advantages of the kd-tree for K-NN nearest neighbor searches in multidimensional, unorganized point clouds compared to exhaustive or brute-force search queries.

You can find my code below. To my surprise, I am not able to find any configuration in which the search space structuring via the tree is more efficient and performs better. Has anyone noticed similar behavior? Are there any functionalities (as with the rather simple pdist2 function) that are not fully documented? I'm less interested in the most efficient search than in a simple performance comparison.

Thank you very much

samples_all=ceil(linspace(1000,1000000,100));
dimensions_all=1:1:20;
K=5;

time_kd=NaN(numel(samples_all),numel(dimensions_all));
time_bf=NaN(numel(samples_all),numel(dimensions_all));

close all

for j=1:numel(dimensions_all)
    dimensions=dimensions_all(j);
    disp(j);
    for i=1:numel(samples_all)
        samples=samples_all(i);
        pc1=rand(samples,dimensions); 
        pc2=rand(samples,dimensions);
        % pc1=randn(samples,dimensions); 
        % pc2=randn(samples,dimensions);
        tic
        [~] =knnsearch(pc1',pc2','NSMethod','kdtree','K',K);
        time_kd(i,j)=toc;

        tic
        % [~] = knnsearch(pc1',pc2','NSMethod','exhaustive','K',K);
        [~]=pdist2(pc1',pc2','Euclidean','Smallest',K);
        time_bf(i,j)=toc;  
    end

    figure(1);
    hold on
    p=surf(samples_all,dimensions_all,medfilt2(time_kd',[3 5],'symmetric'));
    p.EdgeColor='none';
    p.FaceColor=[0.8500 0.3250 0.0980];
    p.FaceAlpha=.5;
    p=surf(samples_all,dimensions_all,medfilt2(time_bf',[3 5],'symmetric'));
    p.EdgeColor='none';
    p.FaceColor=[0 0.4470 0.7410];
    p.FaceAlpha=.5;
    hold off
    xlabel('samples');
    ylabel('dimensions');
    zlabel('computing time / s');
    legend('kd-tree','brute-force');
    grid on
    view(-45,45);
    title(['K=',num2str(K)]);
    drawnow();
end

Answer 1

[Harsh]

Hi @Lennart Hinz,

I would recommend you to only measure the search time with the KD-tree, make sure the “KDTreeSearcher” object is created before your “tic” and “toc” calls for knnsearch.

Here's how to adjust your code around line 15 to exclude the tree construction time from your performance measurement:

mdl = KDTreeSearcher(pc1'); % Construct the tree BEFORE starting the timer

tic
[~] = knnsearch(mdl,pc2','K',K); % Measure only the search time
%% the code goes on %%

This way, you will be comparing the brute-force search time directly against the KD-tree's query time, which is where its efficiency typically shines for repeated searches.

Here's a result I was able to get with a similar script after making these changes.

I hope this helps, thanks!

[Lennart Hinz]

Thank you for your feedback and I apologize for the delay in replying. The week-long Matlab outage has caused some complications...

Although for some problems it can be useful to separate tree construction and tree access, in my view both should be considered together for a fair comparison in order to obtain a plausible statement about possible runtime advantages wrt exhaustive search.

From my point of view, the pdist2 query is too good.

Nevertheless, thank you very much for your feedback!

Lennart

[Harsh]

I agree with both should be considered together for a fair comparison. However, when evaluating the performance of the kd-tree in MATLAB, this seems to be the only viable option.

As an alternative, I recommend trying languages like C++ or Rust, which can handle larger datasets more efficiently. There, you will see the KD-Tree answering queries faster than the brute-force approach.