Skip to main content
USENIX
  • Conferences
  • Students
Sign in
  • OSDI '12 Home
  • Organizers
  • Registration Information
  • Registration Discounts
  • At a Glance
  • Calendar
  • Technical Sessions
  • Workshops
  • Poster Sessions and Receptions
  • Birds-of-a-Feather Sessions
  • Sponsors
  • Activities
  • Hotel and Travel Information
  • Services
  • Students
  • Questions
  • Help Promote
  • For Participants
  • Call for Papers
  • Past Proceedings

sponsors

Diamond Sponsor
Diamond Sponsor
Gold Sponsor
Gold Sponsor
Silver Sponsor
Silver Sponsor
Silver Sponsor
Silver Sponsor
Silver Sponsor
Bronze Sponsor
Bronze Sponsor
Bronze Sponsor
General Sponsor
General Sponsor
General Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor
Media Sponsor

twitter

Tweets by @usenix

usenix conference policies

  • Event Code of Conduct
  • Conference Network Policy
  • Statement on Environmental Responsibility Policy

You are here

Home » GraphChi: Large-Scale Graph Computation on Just a PC
Tweet

connect with us

http://twitter.com/usenix
https://www.facebook.com/events/284007718333937/
http://www.linkedin.com/groups/USENIX-Association-49559/about
http://www.youtube.com/user/USENIXAssociation

GraphChi: Large-Scale Graph Computation on Just a PC

Authors: 

Aapo Kyrola and Guy Blelloch, Carnegie Mellon University; Carlos Guestrin, University of Washington

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. 

Aapo Kyrola, Carnegie Mellon University

Guy Blelloch, Carnegie Mellon University

Carlos Guestrin, University of Washington

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.

BibTeX
@inproceedings {180252,
author = {Aapo Kyrola and Guy Blelloch and Carlos Guestrin},
title = {GraphChi: Large-Scale Graph Computation on Just a {PC}},
booktitle = {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} Association},
month = oct,
}
Download
Kyrola PDF
View the slides

Presentation Video

Presentation Audio

MP3 Download OGG Download

Download Audio

  • Log in or    Register to post comments

Diamond Sponsors

Gold Sponsors

Silver Sponsors

Bronze Sponsors

General Sponsors

Media Sponsors & Industry Partners

© USENIX

  • Privacy Policy
  • Conference Policies
  • Contact Us