Fast 2D distance calculation

Hi all,

Many of the codes I am currently using depend on a simple calculation: the distance between a single point and a set of other points.

In one example, using the matlab profiler I see that this single calculation takes 50% of the total function time, so I would like to optimise it as far as possible.

I have looked around and haven't found anything more optimal than:

p1 = rand(1,2); % single point
pn = rand(1000000,2); % random points

tic
d = sqrt(sum((p1-pn).^2,2)); % calculate the distance between these
toc

Does anyone else have a clever idea that would optimise this - even just by a tiny fraction? Is there any way to speed these calculations up on the GPU or using a mex? I would be really happy to see any suggestions.

I suspect this might be already be as mathematically simple as possible, but I'm frustrated because I need to calculate this a lot.

I have already vectrorised my code as far as possible.

Thanks for any help,

R.

[Adam]

Do you always need the exact distance or just the relative distances? e.g. if you only need to find, for example, which point is closest you can omit the expensive sqrt operation because ordering is unchanged by this. This is used in many contexts as a way to speed up distance-based calculations where the exact distance itself is not actually needed.

You can test out if using the GPU speeds it up very quickly. Just put it in a GPU array and try it. If you have Matlab Coder you can likewise try a C++ or C equivalent very quickly (or just program your own as it is a trivial function) and test the speed difference.

[Neuropragmatist]

Hmmm, that is very interesting. In some cases I want to Gaussian weight the distances, so I think I do need the exact distance (but I will check if I can modify the Gaussian to work with squared distance).

In other cases though I just want to know how many points are less than some distance D away, so I could forget the sqrt and instead test how many points are less than D^2 away. Testing this I find only a very small speed increase, but it is still an increase, thanks!

[Adam]

How long is this taking you exactly? When I ran it with the profiler on (i.e. in normal usage it should be faster) the distance calculation took 0.027s on your given example.

[Neuropragmatist]

Well the example is just a toy to show what I have come up with so far.

In reality I have to compute the distance between 60000x2 points (minimum) and a 1x2 point 2704 times and I have to do this about 40000 times.

Just doing this once takes my function 10s and 50% of that is purely the line computing the distance equation, so obviously cutting that down would help me a lot time wise.

Unfortunately there is no way for me to this vectorally or in a pairwise way because the number of points varies a lot and can easily require too much memory to compute in a pairwise fashion.

Hope this makes more sense,

R.

[Neuropragmatist]

I have run the following code several times and I get slightly different results:

xi = 1:.5:8;
t1 = NaN(1,8);
t2 = NaN(1,8);
for p = 1:length(xi)
    p1 = rand(1,2);
    pn = rand(ceil(10^xi(p)),2);

    tic;
    d1 = sqrt(sum((pn-p1).^2,2));
    t1(p) = toc;

    tic;
    d2 = pdist2(p1,pn);
    t2(p) = toc;
end

figure
plot(xi,t1,'r',xi,t2,'b');
legend({'Manual','Pdist2'})

Which probably suggests that any differences in time between pdist2 and manual calculation are negligible and more dependent on the current background state of the CPU.

However, generally the manual calculation is slightly faster or both methods are the same.

Answer 1

[Matt J]

If you have the Parallel Computing Toolbox, you can execute the computations on the GPU just by building p1 and pn as gpuArrays. That should definitely speed things up.

gd=gpuDevice;

p1 = gpuArray.rand(1,2); 
pn = gpuArray.rand(1000000,2); 

tic
d = sqrt(sum((p1-pn).^2,2));
wait(gd);
toc  %Elapsed time is 0.001429 seconds.

[Neuropragmatist]

I looked into this and it seems that my (work) PC only has a crappy integrated GPU that is not Matlab compatible...

[Matt J]

Well, I don't think the question can be taken any further until we know what parallel computing resources you do have, or can remote connect to. I think you are at the limits of performance already with standard Matlab.

Answer 2

[Joss Knight]

pdist2 is the usual way to do this, if you have Statistics and Machine Learning Toolbox.

[Neuropragmatist]

From what I have read, computing the distance directly using the equation is faster than using pdist or pdist2 as it avoids the overheads involved with calling the function.

I don't know if this remains true if you are computing pairwise distances, but I only need to know the distance from one point to many other points.

[Joss Knight]

But pdist2 does that. Input x is a 1-by-2 vector, and input y is an N-by-2 array of N points.

You may be right that it is no faster than implementing it manually.