# speedup dsearchn for large data set

12 views (last 30 days)
Michal Kvasnicka on 26 Mar 2018
Commented: Michal Kvasnicka on 27 Mar 2018
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.

John D'Errico on 26 Mar 2018
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

#### 1 Comment

Michal Kvasnicka on 27 Mar 2018
Thanks for hint! knnsearch looks very promising.