Euclidean Distance (huge number of vectors)

I have a 70,000 x 300 matrix. These are basically 70,000 vectors of 300 elements each. I need the distance matrix (distances between each pair of vectors). It is too large to just use pdist. Does anybody have general programming tips on how to handle this problem?

Answer 1

[Richard Brown]

You could do something like this and leave it running overnight :| Obviously you'd define your histogram edges to be relevant to the vectors you were using. The disp statement is purely there as a primitive progress bar

n = 70000;
x = rand(300,n);
edges = linspace(0, 10, 100);
edges2 = edges.^2;
h = zeros(1, numel(edges));

for i = 1:n-1;
    d2 = sum(bsxfun(@minus, x(:, i+1:n), x(:, i)).^2);
    h = h + histc(d2, edges2);
    disp(100*i/n)
end

And then to display it,

bar(edges, h, 'histc')

EDIT Adjusted to reflect Walter Roberson's comment below to eliminate the use of sqrt

[Walter Roberson]

You can steel some efficiency by using the square of the edges in the histc, and not taking the sqrt() in the d calculation. You only care about the distribution of the distances, not about the distances themselves, so the sqrt() is not needed if you adjust the boundaries.

[Richard Brown]

Good point, edited accordingly

[Sean de Wolski]

Nice!

Answer 2

[Image Analyst]

That's 70,000 * 69,999 / 2 = 2.4 billion distances. What are you going to do with all those? Can you figure out a way where you only need to calculate some specific distances for some limited number of specific circumstances/criteria rather than all of them? Do you really need all 2.4 billion of them?

[Vishnu Sreekumar]

I basically need a cumulative histogram of these 2.4 billion distances. So I do need access to all 2.4 billion distances but only to be able to count them. So I'm sure there is a way to do this as smaller computations (and then store them away until I need to count the distances, which I can do one matrix at a time too, it doesn't all have to be in memory at the same time).

[Image Analyst]

If there is not pattern and they're more or less uniformly distributed, then you would probably get the same essential shape of the histogram after only a few thousand distances. You can do that for a few thousand of them, then a few million, and see if the shape of the histogram changes substantially. If the histogram shape equilibrates/stabilizes after a few thousand calculations, why do all 2.4 billion of them?

Answer 3

[Sean de Wolski]

Break it into a bunch of smaller problems and solve each one (based on what you want as an end result).

Some questions to ask yourself: Do the vectors follow any pattern? Could you downsample or merge some of them? What are you doing with the results?

The more background you can give us the more we can help.

Answer 4

[Vishnu Sreekumar]

I need to then count up these distances (basically a histogram of distances). Hope that simplifies the question a little. I was thinking I break the matrix into smaller matrices and then go from there but I'm still not very clear on how to proceed. This is basically a question on how to deal with memory and I'm not a very experienced programmer. Hence seeking advice from the collective wisdom here.