Usenix Association 10th Usenix Symposium on Operating Systems Design and Implementation (osdi '12) 31 Graphchi: Large-scale Graph Computation on Just a Pc
Usenix Association 10th Usenix Symposium on Operating Systems Design and Implementation (osdi '12) 31 Graphchi: Large-scale Graph Computation on Just a Pc
复制标题
DOI：
--
复制
发表时间：
2012-10
期刊：
影响因子：
--
通讯作者：
Aapo Kyrola;G. Blelloch;Carlos Guestrin
中科院分区：
文献类型：
--
作者：
Aapo Kyrola;G. Blelloch;Carlos Guestrin
当前用于图计算的系统需要分布式计算集群来处理非常大的现实世界问题，诸如对社交网络或web图的分析。虽然分布式计算资源已经变得更容易访问，但开发分布式图算法仍然具有挑战性，特别是对于非专家。在这项工作中，我们提出了GraphChi，一个基于磁盘的系统，用于在具有数十亿条边的图形上进行高效计算。通过使用一种众所周知的方法将大图分解为小部分，以及一种新颖的并行滑动窗口方法，GraphChi能够在非常大的图上执行几种高级数据挖掘，图挖掘和机器学习算法，只需使用一台消费级计算机。我们进一步扩展GraphChi，以支持随着时间的推移而演变的图形，并证明，在一台计算机上，GraphChi可以每秒处理超过10万个图形更新，同时执行计算。我们表明，通过实验和理论分析，GraphChi表现良好的SSD和旋转硬盘驱动器。通过重复现有分布式系统的实验报告，我们表明，只有一小部分的资源，GraphChi可以在非常合理的时间内解决同样的问题。我们的工作使得任何拥有现代PC的人都可以进行大规模的图形计算。
Current systems for graph computation require a distributed computing cluster to handle very large real-world problems, such as analysis on social networks or the web graph. While distributed computational resources have become more accessible, developing distributed graph algorithms still remains challenging, especially to non-experts. In this work, we present GraphChi, a disk-based system for computing efficiently on graphs with billions of edges. By using a well-known method to break large graphs into small parts, and a novel parallel sliding windows method, GraphChi is able to execute several advanced data mining, graph mining, and machine learning algorithms on very large graphs, using just a single consumer-level computer. We further extend GraphChi to support graphs that evolve over time, and demonstrate that, on a single computer, GraphChi can process over one hundred thousand graph updates per second, while simultaneously performing computation. We show, through experiments and theoretical analysis, that GraphChi performs well on both SSDs and rotational hard drives. By repeating experiments reported for existing distributed systems, we show that, with only fraction of the resources, GraphChi can solve the same problems in very reasonable time. Our work makes large-scale graph computation available to anyone with a modern PC.