这是可能的,因为PageRank是特征值的一种形式,这就是MapReduce引入的原因。但是在实际实现中似乎存在问题,比如每个从机都要维护一个矩阵的副本?
发布于 2009-04-21 19:30:48
PageRank通过迭代求解网络的稳态离散流条件来解决主导特征向量问题。
如果NxM矩阵A描述了从节点n到节点m的链路权重(流量),则
p_{n+1} = A . p_{n} 在p已经收敛到稳定状态(p_n+1 = p_n)的极限中,这是一个特征值为1的特征向量问题。
PageRank算法不需要将矩阵保存在内存中,但在密集(非稀疏)矩阵上效率较低。对于密集矩阵,MapReduce是错误的解决方案--您需要节点之间的局部性和广泛的交换--您应该转而使用LaPACK和MPI以及其他解决方案。
您可以在wukong library (用于ruby的hadoop streaming )或Heretrix pagerank submodule中看到一个有效的pagerank实现。( heretrix代码独立于Heretrix运行)
(免责声明:我是“悟空”的作者之一。)
发布于 2008-12-24 00:02:07
前同步码
如果对数据进行了正确的隔离,就可以在没有每台机器上的完整数据集的情况下实现并行计算结果。
以下面的循环为例:
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];
}
}显然,像上面这样的循环会变得非常有问题(注意矩阵索引器)。但是,确实存在展开这些类型的循环并创建有效的并行算法的技术。
应答
谷歌可能开发了一种解决方案来计算特征值,而不需要在所有从属计算机上维护矩阵的副本。-或者-他们使用类似Monte Carlo或其他Approximation Algorithm的东西来开发“足够接近”的计算。
事实上,我甚至可以说,谷歌将尽最大努力使其PageRank算法所需的任何计算尽可能高效。当您运行these和this之类的机器时(请注意以太网电缆),您不能传输大型数据集(100 is ),因为考虑到它们的硬件限制,这是不可能的。
话虽如此,谷歌擅长于让程序员社区感到惊讶,他们的实现可能会完全不同。
POSTAMBLE
一些很好的并行计算资源包括OpenMP和MPI。这两种并行实现都从非常不同的范例中实现并行计算,其中一些范例源于机器实现(集群与分布式计算)。
发布于 2008-12-24 00:47:47
我怀疑,除了那些具有特殊结构的矩阵(例如,稀疏矩阵或具有某些块模式的矩阵)之外,它对于大多数矩阵都是难以处理的。矩阵系数和特征值之间有太多的耦合。
PageRank使用一种非常特殊形式的sparse matrix,通过计算其特征值得出的任何结论几乎肯定不会扩展到一般矩阵。(编辑:这里是看起来很有趣的another reference )
https://stackoverflow.com/questions/388302
复制相似问题