distance.m

A fully vectorized function that computes the Euclidean distance matrix between two sets of vectors.

Description

A fully vectorized function that computes the Euclidean distance matrix between two sets of vectors.

The output is the same as MathWorks' (Neural Network Toolbox) 'dist' funtion (ie, d = dist(A',B), where A is a (DxM) matrix and B a (DxN) matrix, returns the same as my d = distance(A,B) ), but this function executes much faster.

• Acknowledgements: This submission has inspired the following:; Efficient K-Nearest Neighbor Search using JIT
• MATLAB release: MATLAB 5.2 (R10)

[Jan de Vries]

Fantastic!

[Peter G]

useful...good

[ti saigon]

 

[imad ali]

need the file

[Emily Van Ark]

great, fast little function. Exactly what I was looking for!

[uday desai]

 

[Hsuan-Tien Lin]

great code

[Anton Cervantes]

 

[Babak Taati]

good!

[Catherine Sweeney-Reed]

Great! Thanks!

[Enrique Guevara]

Is a very fast code. Is faster than any other code for any vectors biger that 8 points.

[Markus Buehren]

Simple but nice. Performance can still be improved by about 60% by avoiding calls to repmat:

d = abs(aa( ones(size(bb,2),1), :)' + bb( ones(size(aa,2),1), :) - 2*a'*b);

Markus

[Markus Buehren]

Sorry, I forgot the sqrt:

d = sqrt(abs(aa( ones(size(bb,2),1), :)' + bb( ones(size(aa,2),1), :) - 2*a'*b));

[Xi-Lin Li]

very good code

Thanks

[A. S.]

Very useful, especially Markus' version.

[M. Shoaib Sehgal]

for vectors it simple to compute using:

distance = norm(A-B)

[Panyam Narahari Sastry]

Good

[Philipp Berens]

Quick and clean.

What might be nice: Optional only one argument.

[Oliver Woodford]

Could be faster still by using bsxfun:
d = sqrt(abs(bsxfun(@plus, aa', bb) - 2*a'*b));

[fabio freschi]

According to Oliver Woodford, on my macbook the fastest is

d = sqrt(bsxfun(@plus,dot(a,a,1)',dot(b,b,1))-2*a'*b);

[Stuart Layton]

I find the original code to be faster than the method put forth by oliver
~~~~~~
s = 100000; a = rand(5,s); b = rand(5,1); t = []; n = 1000;
disp(['Data Points: ', num2str(s), ' iterations: ', num2str(n)]);
for i=1:n
    tic; d = distance(a,b); t(i) = toc;
end

disp(['Average run time: ', num2str(mean(t))]);
t = [];
for i=1:n
    tic; d = sqrt(bsxfun(@plus,dot(a,a,1)',dot(b,b,1))-2*a'*b); t(i) = toc;
end
disp(['Average run time: ', num2str(mean(t))]);
~~~~~~

Data Points: 100000 iterations: 1000
Average run time: 0.01356
Average run time: 0.020044

[George]

Why is the -2ab term included?

[T. R.]

 

[Andrea Tacchetti]

Things can go wrong in extreme cases.
If dimensionality is very high numerical errors will kick in.

I have twenty-five hundred 10'000 dimensional vectors stored in matrix X and

~
sum(diag(distance(X',X'))) = 6e-4;
~

Other than that, great job!

[Ali Asghar Torabi]

Thanks. using repmat has made it useful and fast.

[vince]

I find a simple

sqrt((a-b)'*(a-b))

faster to compute the Euclidean distance