speedup dsearchn for large data set

12 visualizaciones (últimos 30 días)
Michal
Michal el 26 de Mzo. de 2018
Comentada: Michal el 27 de Mzo. de 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.

Respuesta aceptada

John D'Errico
John D'Errico el 26 de Mzo. de 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 comentario
Michal
Michal el 27 de Mzo. de 2018
Thanks for hint! knnsearch looks very promising.

Iniciar sesión para comentar.

Más respuestas (0)

Productos

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by