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));endif nargout == 2 d = sqrt(d);endend
I tried to use pdist2 function, see the following function dsn:
function [k,d] = dsn(x,xi)% number of rows xi and init output arraysxirows = 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;endif nargout == 2 d = sqrt(d);endend
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);toctic;k2 = dsn(x,xi);tocisequal(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.
Best Answer