No BSD License  

Highlights from
distance.m

4.6

4.6 | 20 ratings Rate this file 40 Downloads (last 30 days) File Size: 1.28 KB File ID: #71

distance.m

by

 

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

| Watch this File

File Information
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 file inspired Efficient K Nearest Neighbor Search Using Jit and Ipdm: Inter Point Distance Matrix.

MATLAB release MATLAB 5.2 (R10)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (29)
19 Feb 2014 Benoit Thouy

Following the analysis of Stuart Layton, I've found a merely faster way to perform the same computation:

d = sqrt(bsxfun(@minus,bsxfun(@plus,sum(a.^2,1),sum(b.^2,1)'),2*(a'*b).'));

Using the same tool as Stuart Layton (modified to have the tic/toc outside the loop), I measure 4.3607ms for distance.m and 4.1252ms for mine. Does not change dramatically, ok.

11 Nov 2013 Zeeshan

Hi, I am new to this so how would I exactly inputthis on matlab? if anyone can help me please

19 Apr 2012 Arun Kumar Chithanar

Thanks. This saved me time!

21 Sep 2011 vince

I find a simple

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

faster to compute the Euclidean distance

30 Aug 2011 Ali Asghar Torabi

Thanks. using repmat has made it useful and fast.

26 Feb 2011 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!

11 Jan 2011 T. R.  
11 Jan 2011 George

Why is the -2ab term included?

23 Jun 2010 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

07 Apr 2010 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);

25 Nov 2008 Oliver Woodford

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

19 Feb 2008 Philipp Berens

Quick and clean.

What might be nice: Optional only one argument.

26 Dec 2007 Panyam Narahari Sastry

Good

21 Nov 2007 M. Shoaib Sehgal

for vectors it simple to compute using:

distance = norm(A-B)

09 Oct 2007 A. S.

Very useful, especially Markus' version.

17 May 2007 Xi-Lin Li

very good code

Thanks

02 Feb 2007 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));

02 Feb 2007 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

08 Dec 2006 Enrique Guevara

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

15 Apr 2005 Catherine Sweeney-Reed

Great! Thanks!

30 Mar 2005 Babak Taati

good!

02 Mar 2005 Anton Cervantes  
20 Nov 2004 Hsuan-Tien Lin

great code

13 May 2004 uday desai  
09 Apr 2004 Emily Van Ark

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

07 Mar 2004 imad ali

need the file

21 Oct 2003 ti saigon  
15 Apr 2003 Peter G

useful...good

02 Apr 2002 Jan de Vries

Fantastic!

Contact us