MapReduce中大规模图的双nectivity

是 否 +2 论坛币

k人 参与回答

经管之家送您一份

应届毕业生专属福利!

求职就业群

赵安豆老师微信：zhaoandou666

经管之家联合CDA

送您一个全额奖学金名额~ !

立即领取

感谢您参与论坛问题回答

经管之家送您两个论坛币！

+2 论坛币

英文文献：MapReduce中大规模图的双nectivity
英文文献作者：Giorgio Ausiello,Donatella Firmani,Luigi Laura,Emanuele Paracone
英文文献摘要：
最初由谷歌提出的MapReduce框架和它的开源实现Hadoop，现在在工业和学术界都被认为是处理pb规模数据集的标准框架。本文描述了一种求解无向图双连通的两轮MapReduce方法，即图g中连接点集、桥集和双连通分量集的计算方法。桥)是一个顶点(resp。边)其去除增加连接的部件的数量。一个双连通部件是一个最大的双连通子图，即它既不包括连接点也不包括桥。为了使通信成本最小化，该算法基于输入数据集的汇总，这是一种紧凑的数据结构，可以从该数据结构中回答有关双nectivity属性的查询。这个摘要称为导航草图，最初是在数据流框架中设计的，并被隐式地证明具有递增性可维护性。这里我们用不同的框架来定义它，以证明它是可合并的。在分布式或并行计算中，可合并性是摘要的关键属性:特别是，它提供了一种将摘要的计算拆分到原始数据集的不同子集的方法，从而利用MapReduce框架的并行性。最后我们讨论了一个假设机器内存有限的场景，展示了可用内存和算法轮数之间的权衡。在对大规模真实世界图的Hadoop实现的不同执行情况的基础上，我们通过实验分析来总结本文，验证了我们的方法的有效性。

扫码加我 拉你入群

请注明：姓名-公司-职位

以便审核进群资格，未注明则拒绝

分享0 收藏0 回帖