I am looking for significant speed up of dsearchn function in a case of large input data
where is not used triangulation. In this case the relevant part of dsearchn looks like:
function [k,d] = dsearchn_(x,xi)
xirows = size(xi,1);
k = zeros(xirows,1);
d = zeros(xirows,1);
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)
xirows = size(xi,1);
k = zeros(xirows,1);
d = zeros(xirows,1);
stepxirows = 100000;
iloop = 0:stepxirows:xirows;
if iloop(end) ~= xirows
iloop = [iloop,xirows];
end
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.
