Scaling Techniques for Massive Scale-Free Graphs in Distributed (External) Memory

Roger Pearce, Maya Gokhale, Nancy M. Amato

Research output: Chapter in Book/Report/Conference proceedingConference contribution

53 Scopus citations


We present techniques to process large scale-free graphs in distributed memory. Our aim is to scale to trillions of edges, and our research is targeted at leadership class supercomputers and clusters with local non-volatile memory, e.g., NAND Flash. We apply an edge list partitioning technique, designed to accommodate high-degree vertices (hubs) that create scaling challenges when processing scale-free graphs. In addition to partitioning hubs, we use ghost vertices to represent the hubs to reduce communication hotspots. We present a scaling study with three important graph algorithms: Breadth-First Search (BFS), K-Core decomposition, and Triangle Counting. We also demonstrate scalability on BG/P Intrepid by comparing to best known Graph500 results. We show results on two clusters with local NVRAM storage that are capable of traversing trillion-edge scale-free graphs. By leveraging node-local NAND Flash, our approach can process thirty-two times larger datasets with only a 39% performance degradation in Traversed Edges Per Second (TEPS). © 2013 IEEE.
Original languageEnglish (US)
Title of host publication2013 IEEE 27th International Symposium on Parallel and Distributed Processing
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Number of pages12
ISBN (Print)9781467360661
StatePublished - May 2013
Externally publishedYes


Dive into the research topics of 'Scaling Techniques for Massive Scale-Free Graphs in Distributed (External) Memory'. Together they form a unique fingerprint.

Cite this