MATLAB Central Newsreader - euclidean distance

euclidean distance

kudrah — Tue, 30 Jun 2009 19:31:01 -0400

Hi everyone!
Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???

for i=1:size(A,1);
for k=1:size(B,1);
Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
end
end

Thank you in advance!!!!

Re: euclidean distance

Stefan Stefan — Tue, 30 Jun 2009 21:25:03 -0400

First I would advise to preallocate the resulting matrix like

Eucl_Ideal=zeros(size(A,1),size(B,1));

in advance to the for loop.

Regards,
Stefan

"kudrah " <elzarogia@yahoo.gr> wrote in message <h2dp5l$p98$1@fred.mathworks.com>...
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end
>
> Thank you in advance!!!!

Re: euclidean distance

John D'Errico — Tue, 30 Jun 2009 22:53:01 -0400

"kudrah " <elzarogia@yahoo.gr> wrote in message <h2dp5l$p98$1@fred.mathworks.com>...
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end
>
> Thank you in advance!!!!

This matrix will take roughly 300 megabytes to store.
This is one reason why it takes forever. A bigger reason
for the slowness is that you failed to preallocate the
memory.

Finally, you might convert to single precision to store
the distances, so this might work best:

D = bsxfun(@times,single(A(:,1)),single(B(:,1)).');
D = D + bsxfun(@times,single(A(:,2)),single(B(:,2)).');
D = D + bsxfun(@times,single(A(:,3)),single(B(:,3)).');
D = sqrt(D);

HTH,
John

Re: euclidean distance

Peter Perkins — Wed, 01 Jul 2009 14:25:26 -0400

kudrah wrote:
> Hi everyone!
> Im trying to calculate the euclidean distance between 2 matrices that contain 3d points.The matrices are quite large,eg A=19500x3 and B=2000x3.I want to calculate the distance between each point of A to each point of B and thus produce a 19500x2000 matrix.So far i wrote this but it takes like forever..Is there any faster way???
>
> for i=1:size(A,1);
> for k=1:size(B,1);
> Eucl_Ideal(i,k)=norm(A(i,:)-B(k,:));
> end
> end

As others have said, preallocate the result. Also:

Because of the way data is stored in MATLAB, your loops are in the wrong order -- you want to have the row index in Eucl_Ideal varying fastest or you will be accessing memory very non-sequentially.

But most likely, you want to loop over 1:3 within 1:2000, and sum the squared diffs for each dimension of each point in B to all points in A, vectorized. This is essentially what John suggested with BSXFUN (though I think those ought to be @minus's, wrapped in .^2's). Here's an "unrolled loop" version.

Eucl_Ideal = zeros(size(A,1),size(B,1));
for i = 1:size(B,1);
Eucl_Ideal(:,i) = sqrt((A(:,1)-B(i,1)).^2 + (A(:,2)-B(i,2)).^2 + (A(:,3)-B(i,3)).^2);
end

There's a good deal that can be learned about memory access and vectorization from this example. Hope this helps.

Re: euclidean distance

oruganti murthy — Thu, 02 Jul 2009 03:24:01 -0400

Hi peter,
Thank you very much.
Your solution was very helpful to me in my situation (except that I have 150 dimensions instead of 3 !).
In my situation, I just need the index (of point) of B which is nearest to each point in B. Instead of finding the pairwise distance and using min command, can I bypass this laborious calculation of calculating Euclidean distance to directly arrive at the indices.

regards,
ramana

> But most likely, you want to loop over 1:3 within 1:2000, and sum the squared diffs for each dimension of each point in B to all points in A, vectorized. This is essentially what John suggested with BSXFUN (though I think those ought to be @minus's, wrapped in .^2's). Here's an "unrolled loop" version.
>
> Eucl_Ideal = zeros(size(A,1),size(B,1));
> for i = 1:size(B,1);
> Eucl_Ideal(:,i) = sqrt((A(:,1)-B(i,1)).^2 + (A(:,2)-B(i,2)).^2 + (A(:,3)-B(i,3)).^2);
> end
>
> There's a good deal that can be learned about memory access and vectorization from this example. Hope this helps.