There has been a recent explosion in specialized graph computing frameworks with different classes of framework addressing different niches of requirements. Specifically, some are designed for graphs that fit in a single machine's memory, but fail when the graph exceeds memory size. Other frameworks handle extremely large graphs that exceed a single ma- chine's memory, but achieve worse performance than simple C programs on small graphs. Thus, the current state-of-the-art requires users to adopt one programming framework for small graphs and a completely different framework for large graphs. In this thesis, we present GraphZ and GraphStone.

GraphZ has 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.3x over existing state-of-the-art solutions. In addition, GraphZ's reduced IO greatly reduces power consumption, resulting in tremendous energy savings.

GraphStone is a unified framework that outperforms current best-in-class approaches for both in-memory and out-of-core graph computing. GraphStone's key contribution is an execution model which combines the best merits of bulk synchronous and asynchronous updates to achieve the parallelism and streaming data access of bulk synchronous models with the fast convergence time of asynchronous models. We implement GraphStone in C++ and compare its performance to best-in-class approaches for both in-memory and out-of-core computing. We find that GraphStone programs require no modification when moving from small to large graphs, yet GraphStone is 2.5x faster than a state-of-the-art in-memory approach and 11.6x faster than a popular, robust out-of-core approach.