首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >如何用MapReduce/Hadoop实现特征值计算?

问如何用MapReduce/Hadoop实现特征值计算?
EN

Stack Overflow用户
提问于 2008-12-23 06:29:45
回答 5查看 6.6K关注 0票数 10

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

EN

回答 5

Stack Overflow用户

发布于 2009-04-21 19:30:48

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

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

代码语言:javascript
复制
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运行)

(免责声明:我是“悟空”的作者之一。)

票数 9
EN

Stack Overflow用户

发布于 2008-12-24 00:02:07

前同步码

如果对数据进行了正确的隔离,就可以在没有每台机器上的完整数据集的情况下实现并行计算结果。

以下面的循环为例:

代码语言:javascript
复制
for (int i = 0; i < m[].length; i++)
{
    for (int j = 0; j < m[i].length; j++)
    {
        m[i][j]++; 
    }
}

并给出一个如下布局的矩阵:

代码语言:javascript
复制
       j=0   j=1   j=2
 i=0  [   ] [   ] [   ]
 i=1  [   ] [   ] [   ]
 i=2  [   ] [   ] [   ]

存在并行构造,使得J列可以被发送到每台计算机,并且单个列被并行计算。当你得到一个包含依赖项的循环时,并行化的困难就来了。

代码语言:javascript
复制
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。这两种并行实现都从非常不同的范例中实现并行计算,其中一些范例源于机器实现(集群与分布式计算)。

票数 6
EN

Stack Overflow用户

发布于 2008-12-24 00:47:47

我怀疑,除了那些具有特殊结构的矩阵(例如,稀疏矩阵或具有某些块模式的矩阵)之外,它对于大多数矩阵都是难以处理的。矩阵系数和特征值之间有太多的耦合。

PageRank使用一种非常特殊形式的sparse matrix,通过计算其特征值得出的任何结论几乎肯定不会扩展到一般矩阵。(编辑:这里是看起来很有趣的another reference )

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/388302

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档