10

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

4

5 回答 5

9

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

如果 NxM 矩阵 A 描述了从节点 n 到节点 m 的链接权重（流量），那么

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

在 p 收敛到稳态的极限 (p_n+1 = p_n) 中，这是一个特征值为 1 的特征向量问题。

PageRank 算法不需要将矩阵保存在内存中，但在密集（非稀疏）矩阵上效率低下。对于密集矩阵，MapReduce 是错误的解决方案——您需要节点之间的局部性和广泛的交换——您应该转而查看 LaPACK 和 MPI 及其朋友。

您可以在 wukong库（用于 ruby​​ 的 hadoop 流）或Heretrix pagerank 子模块中看到有效的 pagerank 实现。（heretrix 代码独立于 Heretrix 运行）

（免责声明：我是悟空的作者。）

于 2009-04-21T19:30:47.663 回答
6

序言：

给定正确的数据隔离，无需每台机器上的完整数据集就可以实现并行计算结果。

以下面的循环为例：

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 卡的硬件限制，这是不可能的。

话虽如此，谷歌擅长让程序员社区感到惊讶，他们的实现可能完全不同。

邮差：

一些用于并行计算的好资源包括OpenMP和MPI。两种并行实现都从非常不同的范式处理并行计算，其中一些源于机器实现（集群与分布式计算）。

于 2008-12-24T00:02:06.883 回答
1

我怀疑除了具有特殊结构的矩阵（例如稀疏矩阵或具有某些块模式的矩阵）之外，大多数矩阵都难以处理。矩阵系数和特征值之间的耦合太多了。

PageRank 使用特殊形式的非常稀疏的矩阵，计算其特征值的任何结论几乎肯定不会扩展到一般矩阵。（编辑：这是另一个看起来很有趣的参考）

于 2008-12-24T00:47:47.040 回答
1

我现在可以回答自己了。PageRank 算法利用稀疏矩阵，它应该在特征值处收敛，并有几个自乘。因此，在 PageRank 实践中，Map/Reduce 过程是有效的。您可以在 Map 过程中执行矩阵乘法，并在 Reduce 过程中形成稀疏矩阵。但是对于一般的矩阵特征值查找，这仍然是一个棘手的问题。

于 2009-01-01T14:28:21.557 回答
1

apache hama项目有一些有趣的 Jacobi 特征值算法实现。它在hadoop上运行。请注意，旋转发生在矩阵的扫描中，而不是在 map reduce 中。

于 2010-02-08T23:53:46.343 回答