speedup dsearchn for large data set

I am looking for significant speed up of dsearchn function in a case of large input data

k = dsearchn(X,XI)

where is not used triangulation. In this case the relevant part of dsearchn looks like:

function [k,d] = dsearchn_(x,xi)
% number of rows xi and init output arrays
xirows = size(xi,1);
k = zeros(xirows,1);
d = zeros(xirows,1);
% nearest point loop (by dsearchn)
for i = 1:xirows
  [d(i),k(i)] = min(sum((x-xi(i,:)).^2,2));
end
if nargout == 2
  d = sqrt(d);
end
end

I tried to use pdist2 function, see the following function dsn:

function [k,d] = dsn(x,xi)
% number of rows xi and init output arrays
xirows = size(xi,1);
k = zeros(xirows,1);
d = zeros(xirows,1);
% nearest point evaluation (by pdist2)
stepxirows = 100000; % set size of xiblock by available memory
iloop = 0:stepxirows:xirows;
if iloop(end) ~= xirows
    iloop = [iloop,xirows];
end
% xiblock loop
for i = 1:length(iloop)-1
    iblock = iloop(i)+1:iloop(i+1);
    xiblock = xi(iblock,:);
    [di,ki] = min(pdist2(x,xiblock,'squaredeuclidean'),[],1);
    k(iblock) = ki;
    d(iblock) = di;
end
if nargout == 2
    d = sqrt(d);
end
end

with speedup (~2x), but it is still not enough for me.

Example:

x =100*rand(1e4,6);
xi=100*rand(1e6,6);
tic;
k1 = dsearchn_(x,xi);
toc
tic;
k2 = dsn(x,xi);
toc
isequal(k1,k2)
nnz(k1-k2)

The results k1 and k2 are identical (in some cases not, due to the internal numerical properties of pdist2).

Some speed up is possible to get by transform input data to the single class

k2 = dsn(single(x),single(xi));

but this is still not enough for me.

I there any other possible way how to speed up the nearest point search? Any search based on triangulation is not viable by enormous memory requirements.

Answer 1

[John D'Errico]

I'd be looking for a different tool than dsearchn, which has been around a while. knnsearch comes to mind.

X = randn(1000,3);
T = delaunayn(X);

xtest = randn(10000,3);

timeit(@() dsearchn(X,T,xtest))
ans =
           0.0221068111935

timeit(@() knnsearch(X,xtest))
ans =
           0.0078199651935

[Michal]

Thanks for hint! knnsearch looks very promising.