The wide availability of powerful and inexpensive cloud computing services naturally motivates the study of distributed graph layout algorithms, able to scale to very large graphs. Nowadays, to process Big Data, companies are increasingly relying on PaaS infrastructures rather than buying and maintaining complex and expensive hardware. So far, only a few examples of basic force-directed algorithms that work in a distributed environment have been described. Instead, the design of a distributed multilevel force-directed algorithm is a much more challenging task, not yet addressed. We present the first multilevel force-directed algorithm based on a distributed vertex-centric paradigm, and its implementation on Giraph, a popular platform for distributed graph algorithms. Experiments show the effectiveness and the scalability of the approach. Using an inexpensive cloud computing service of Amazon, we draw graphs with ten million edges in about 60 minutes.
翻译：强大而廉价的云计算服务的广泛可得性自然激励着对分布式图表布局算法的研究,这种算法能够推广到非常大的图表。 如今,为了处理大数据,公司越来越多地依赖PaAS基础设施,而不是购买和维护复杂和昂贵的硬件。到目前为止,只描述了几个在分布式环境中起作用的基本的、以力量为主的、以力量为主的算法的例子。相反,设计分布式多层次的、以力量为主的算法是一项挑战性更大的任务,但尚未得到解决。我们根据分布式的脊椎中心模式提出了第一种多层次的、以力量为主的算法,并在Giraph(分布式图表算法的流行平台)上应用了这一算法。实验显示了这种方法的有效性和可缩放性。我们使用亚马逊的廉价云计算服务,在大约60分钟内绘制了1 000万个边缘的图表。
相关内容
微信扫码咨询专知VIP会员