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 ยป PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs
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

PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

Website Maintenance Alert

Due to scheduled maintenance, the USENIX website will not be available on Tuesday, December 17, from 10:00 am to 2:00 pm Pacific Daylight Time (UTC -7). We apologize for the inconvenience.

If you are trying to register for Enigma 2020, please complete your registration before or after this time period.

Authors: 

Joseph E. Gonzalez, Yucheng Low, Haijie Gu, and Danny Bickson, Carnegie Mellon University; Carlos Guestrin, University of Washington

Abstract: 

Large-scale graph-structured computation is central to tasks ranging from targeted advertising to natural language processing and has led to the development of several graph-parallel abstractions including Pregel and GraphLab. However, the natural graphs commonly found in the real-world have highly skewed power-law degree distributions, which challenge the assumptions made by these abstractions, limiting performance and scalability.

In this paper, we characterize the challenges of computation on natural graphs in the context of existing graphparallel abstractions. We then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction we introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. We provide a detailed analysis and experimental evaluation comparing PowerGraph to two popular graph-parallel systems. Finally, we describe three different implementation strategies for PowerGraph and discuss their relative merits with empirical evaluations on large-scale real-world problems demonstrating order of magnitude gains.

Joseph E. Gonzalez, Carnegie Mellon University

Yucheng Low, Carnegie Mellon University

Haijie Gu, Carnegie Mellon University

Danny Bickson, 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 {180251,
author = {Joseph E. Gonzalez and Yucheng Low and Haijie Gu and Danny Bickson and Carlos Guestrin},
title = {PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs},
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 = {17--30},
url = {https://www.usenix.org/conference/osdi12/technical-sessions/presentation/gonzalez},
publisher = {{USENIX}},
}
Download
Gonzalez PDF
View the slides

Presentation Video

Download 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