如何使用MapReduce/Hadoop实现特征值计算？

这是可能的,因为PageRank是一种特征值形式,这就是MapReduce引入的原因.但是在实际实现中似乎存在问题,例如每台从属计算机都必须维护矩阵的副本？

PageRank通过迭代求解网络的稳态离散流条件来解决主导特征向量问题.

如果NxM矩阵A描述了从节点n到节点m的链路权重(流量),那么

p_{n+1} = A . p_{n} 

在p已经收敛到稳定状态(p_n + 1 = p_n)的极限中,这是特征值1的特征向量问题.

PageRank算法不要求矩阵保存在内存中,但在密集(非稀疏)矩阵上效率低.对于密集矩阵,MapReduce是错误的解决方案 - 您需要在节点之间进行局部性和广泛交换 - 而您应该看看LaPACK和MPI以及朋友.

你可以在wukong 库中看到一个有效的pagerank实现(hadoop流为ruby)或者在Heretrix pagerank子模块中.(heretrix代码独立于Heretrix运行)

(免责声明:我是悟空的作者.)

前言:

给定正确的数据隔离,可以在每台机器上没有完整的数据集的情况下实现并行计算结果.

以下面的循环为例:

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        m[i][j]++; 
    }
}

并给出以下布局的矩阵:

       j=0   j=1   j=2
 i=0  [   ] [   ] [   ]
 i=1  [   ] [   ] [   ]
 i=2  [   ] [   ] [   ]

存在并行构造,使得可以将J列发送到每个计算机并且并行地计算单个列.当您拥有包含依赖项的循环时,并行化的难点就出现了.

for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        //For obvious reasons, matrix index verification code removed
        m[i][j] = m[i/2][j] + m[i][j+7]; 
    }
}

显然,像上面那样的循环变得极其成问题(注意矩阵索引器.)但是存在用于展开这些类型的循环并创建有效的并行算法的技术.

答案:

谷歌有可能开发出一种计算特征值的解决方案,而无需在所有从属计算机上维护矩阵的副本.- 或 - 他们使用蒙特卡罗或其他一些近似算法来开发"足够接近"的计算.

实际上,我甚至会说Google会尽可能地尽可能地使其PageRank算法所需的任何计算尽可能高效.当你运行这些和这样的机器(注意以太网电缆)时,你无法传输大型数据集(100次演出),因为鉴于商用NIC卡的硬件限制,这是不可能的.

话虽如此,谷歌擅长令程序员社区感到惊讶,他们的实施可能完全不同.

POSTAMBLE:

并行计算的一些好资源包括OpenMP和MPI.两种并行实现都采用非常不同的范式进行并行计算,其中一些范式源于机器实现(集群与分布式计算).