MATLAB,如何在不超出内存约束的情况下计算大坐标集之间的距离？

Question

(使用MATLAB)我有一个大的坐标矩阵和一个大的稀疏邻接矩阵,其坐标相互连接.我曾经问过SO,如何在这个SO问题中有效地计算这些距离,但我现在遇到了内存问题,这是一个更严重的问题.

我使用这个MATLAB函数来计算距离矩阵,Dists = pdist2(fruchterman_graph(:,:),fruchterman_graph(:,:),'euclidean');但它在速度和最终内存的大型网络上都失败了.

这是仅在小图表(不是数十万)上运行的代码:

coordinate = kamada_graph;
    [n, d] = size(kamada_graph);
    assert(d == 2);
    resi = sparse(adj*  spdiags((1:n)',0,n,n));
    resj = sparse(spdiags((1:n)',0,n,n) * adj);
    res = sparse(n,n);
    f = find(adj);  
    res(f) = sqrt((coordinate(resi(f), 1) - coordinate(resj(f), 1)) .^ 2 +...
                          (coordinate(resi(f), 2) - coordinate(resj(f), 2)) .^ 2);

这在大图上创建

??? 使用==>发现错误Matrix太大而无法返回线性索引.
使用[i,j] = find(S)用于稀疏矩阵.
在==> modularize_graphs时出错49 [f] = find(adj);

我更改了被称为的行:

[i,j] = find(ajd);    
res(i,j) = sqrt((coordinate(resi(i,j), 1) - coordinate(resj(i,j), 1)) .^ 2 +...
    (coordinate(resi(i,j), 2) - coordinate(resj(i,j), 2)) .^ 2);

现在在小网络上(~500个顶点)的错误:

??? 内存不足.
键入HELP MEMORY以获取选项.
在==> modularize_graphs 50处出错
res(i,j) = sqrt((coordinate(resi(i,j), 1) - coordinate(resj(i,j), 1)) .^ 2 +...

反正是有使用邻接矩阵和坐标矩阵,计算距离矩阵(N,2)的x,y值,而不陷入内存问题,并可能变得无法太慢呢？

期望的输出是距离矩阵,即根据Adj邻接矩阵连接的所有点之间的距离.

Answer 1

要使用最少量的内存计算逐点距离，您始终可以逐元素迭代邻接矩阵：

%# assuming a square and symmetric adjacency matrix
nCoords = size(adjMat,1);

%# there are at most (n^2-n) distances 
%# if this runs out of memory already, there 
%# is a way to only store existing distances to save 
%# even more memory
distances = NaN((nCoords^2-nCoords)/2,1);

ct = 0;
for row = 1:nCoords
   for col = 1:row-1
     ct = ct+1;
     if adjacencyMatrix(row,col)
        distances(ct) = sum( (coordinate(row,:)-coordinate(col,:)).^2 );
     end
   end
end

distances = sqrt(distances);

使用稀疏方法，您可能想尝试以下方法（我认为您不需要resi和resj，除非我完全误解了您的问题）。

[row,col]=find(adjacencyMatrix);

distances = sqrt(sum( (coordinate(row,:) - coordinate(col,:)).^2 ,2));

sparseDistanceMatrix = sparse(row,col,distances);