Grafu: Unleashing the Full Potential of Future Value Computation for Out-of-core Synchronous Graph Processing

As graphs exponentially grow recently, out-of-core graph systems have been invented to process large-scale graphs by keeping massive data in storage. Among them, many systems process the graphs iteration-by-iteration and provide synchronous semantics that allows easy programmability by forcing the computation dependency of vertex values between iterations. On the other hand, although future value computation is an effective IO optimization for out-of-core graph systems by computing vertex values of future iterations in advance, it is challenging to take full advantage of future value computation while guaranteeing iteration-based dependency. In fact, based on our investigation, even state-of-the-art work along this direction has a wide gap from optimality in IO reduction and further requires substantial overhead in computation as well as extra memory consumption.