GraphChi: Large-Scale Graph Computation on Just a PC
Open access to the papers is sponsored by USENIX.
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.
Authors:
Aapo Kyrola and Guy Blelloch, Carnegie Mellon University; Carlos Guestrin, University of Washington
Open Access Content
Papers are restricted to registered attendees until the event begins. Once the event begins, the content becomes free and open to everyone. Journal articles are open to everyone upon publication. If available, video, audio, and/or slides of this presentation will be posted here after the event.
@inproceedings {180252,
author = {Aapo Kyrola and Guy Blelloch and Carlos Guestrin},
title = {GraphChi: Large-Scale Graph Computation on Just a PC},
booktitle = {Presented as part of the 10th USENIX Symposium on Operating Systems Design and Implementation (OSDI 12)},
year = {2012},
isbn = {978-1-931971-96-6},
address = {Hollywood, CA},
pages = {31--46},
url = {https://www.usenix.org/conference/osdi12/technical-sessions/presentation/kyrola},
publisher = {USENIX},
}
<br><a href="/biblio/export/bibtex/180252">Download</a>
Abstract:
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.
connect with us