How to get around out of memory issue

Question

Itzik Ben Shabat 2015-5-21

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/217914-how-to-get-around-out-of-memory-issue

评论： Itzik Ben Shabat 2015-5-22

Hi, I have a set of 3d points (x,y,z). I wish to compute the distance between every point and all of the other points in the set. so this is the code hat does this:

 nPoints=size(Points, 1);
 [idx, ~] = ndgrid(uint32(1:nPoints),uint32(1:nPoints)); %row indices to calculate distance between
 CartesianDistance = arrayfun(@(row1, row2) norm(Points(row2, 1:3) - Points(row1, 1:3)), idx, idx');

The problem is that now i have 80000 points. and i get an out of memory error (an 80000X80000 matrix does that).note that it is very likely that i will have even more points in the futre. is there a way to go around this out of memory issue ?

0 个评论
显示 -2更早的评论隐藏 -2更早的评论

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Alfonso Nieto-Castanon 2015-5-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/217914-how-to-get-around-out-of-memory-issue#answer_179925

If your end-goal is to actually compute that entire 80000 x 80000 matrix, and you do not have enough memory to keep that matrix, there is no much that you are going to be able to do (perhaps store it into a file instead of keeping it in memory?). But typically your end-goal goes beyond "computing" that matrix (e.g you may want to find the closest point to each of your points, or you may want to use this matrix for clustering your points, etc.). If you let us know what you want to use this matrix for perhaps we can figure out some trick that avoids the need to compute and keep in memory that entire matrix (see for example this cody problem )...

3 个评论
显示 1更早的评论隐藏 1更早的评论

Itzik Ben Shabat 2015-5-21

在 MATLAB Online 中打开

ok so i will give the bigger picture. what i actually want to compute is a dissimilarity measure between the points. This measure is a function of the distance between the points and a feature matrix which contains a histogram vector for each point. so you are correct, i dont need the matrix, i just need the dissimilarity measure (which is a vector in the length of the number of points) so my function basically looks like this :

function [DisMap]=DissimilarityMap(Points,Features)
%DissimilarityMap calculates the dissimilarity between every point in the point
%cloud data set Points
%INPUT:
%Points: 3XN vector containing x,y,z point coordinates
%Features: an MXN matrix containing the feature vectors of every point
nPoints=size(Points, 1);
 [idx, ~] = ndgrid(uint32(1:nPoints),uint32(1:nPoints)); %row indices to calculate distance between
CartesianDistance = arrayfun(@(row1, row2) norm(Points(row2, 1:3) - Points(row1, 1:3)), idx, idx');
FeatureDistance = arrayfun(@(row1, row2) sum(((Features(row2, :) - Features(row1, :)).^2)./(Features(row2, :) + Features(row1, :))), idx, idx');
dH=CartesianDistance.*FeatureDistance;
Dhigh=1-exp(-(1/nPoints)*sum(dH));
DisMap=Dhigh;
end

is there a way to get around it ?

Alfonso Nieto-Castanon 2015-5-21

编辑：Alfonso Nieto-Castanon 2015-5-21

在 MATLAB Online 中打开

In its current form, the only simplification I can think of would be to compute this measure in a for loop separately for each column of your distance matrix (since at the end you are only interested in the sum of dH across each column). That would trade the memory requirement for speed.

Alternatively if you simplify your dissimilarity measure formula perhaps you can also arrive a fast-computation implementation using simple linear algebra tricks (e.g. summing of squared distances can be done much faster, but summing root sum square differences cannot)

EDIT: just to add an example, if your measure was only based on cartesian distances (e.g. dH = CartesianDistance.^2 instead of dH = CartesianDistance.*FeatureDistance ), you could get the alternative dHigh measure directly (without for loop or full distance matrix computation) using:

 normPoints = sum(Points.^2,2);
 dH_mean = normPoints + mean(normPoints) - 2*Points*mean(Points,1)';
 Dhigh = 1-exp(-dH_mean);

that involves O(nPoints) instead of O(nPoints^2) operations so it gets done considerably faster (not that this dissmilarity measure would be particularly useful, only posting as an example of how one goes about simplifying/speeding-up computations).

Itzik Ben Shabat 2015-5-22

thanks for the answer but i have to use this dissimilarity measure. guess ill start for looping now. thanks:)

请先登录，再进行评论。

Answer 2

Jan 2015-5-21

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/217914-how-to-get-around-out-of-memory-issue#answer_179907

By this method your output has 80'000^2*8 Byte = 51.2 GB . Therefore either use a 64 bit machine and install a lot of RAM - a fair guess is the double size of the largest used matrix.

But the distance matrix is symmetric and half of the information is redundant. So better use a smarter way to calculate the pairwise distances. Beside Matlab's pdist there are many tools in the FileExchange, simply search them: http://www.mathworks.com/matlabcentral/fileexchange/?utf8=%E2%9C%93&term=pairwise+distance

But a general problem remains: The more points you have, the larger is the output. But do you really need all distances? Usually there is a smarter way to obtain the required information.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Itzik Ben Shabat 2015-5-21

an explanation of exactly what i wish to accomplish is attached as a comment to the next answer. is there a better way to get the dissimilarity measure?

请先登录，再进行评论。