GraphZ: Improving the Performance of Large-Scale Graph Analytics on Small-Scale Machines

Zhixuan Zhou; Henry Hoffmann. 21 January, 2018.
Communicated by Henry Hoffmann.


Recent programming frameworks enable small computing systems to achieve high performance on large-scale graph analytics by supporting out-of-core graph analytics (i.e., processing graphs that exceed main memory capacity). These frameworks make out-of-core programming easy by automating the tedious process of scheduling data transfer between memory and disk. This paper presents two innovations that improve the performance of software frameworks for out-of-core graph analytics. The first is degree-ordered storage, a new storage format that dramatically lowers book-keeping overhead when graphs are larger than memory. The second innovation replaces existing static messages with novel ordered dynamic messages which update their destination immediately, reducing both the memory required for intermediate storage and IO pressure.We implement these innovations in a framework called GraphZ—which we release as open source—and we compare its performance to two state-of-the-art out-of-core graph frameworks. For graphs that exceed memory size, GraphZ’s harmonic mean performance improvements are 1:8–8:3 over existing state-of-the-art solutions. In addition, GraphZ’s reduced IO greatly reduces power consumption, resulting in tremendous energy savings.

Original Document

The original document is available in PDF (uploaded 21 January, 2018 by Henry Hoffmann).