A Single Machine System for Querying Big Graphs with PRAM

This paper develops Planar (Plug and play PRAM), a single-machine system for graph analytics by reusing existing PRAM algorithms, without the need for designing new parallel algorithms. Planar supports both out-of-core and in-memory analytics. When a graph is too big to fit into the memory of a machine, Planar adapts PRAM to limited resources by extending a fix point model with multi-coreparallelism, using disk as memory extension. For an in-memory task, it dedicates all available CPU cores to the task, and allow sparallelly scalable PRAM algorithms to retain the property, i.e., the more cores are available, the less runtime is taken. We develop a graph partitioning and work scheduling strategy to accommodate sub graph I/O, balance memory usage and reduce runtime, beyond traditional partitioners for multi-machine systems. Using real-life graphs, we empirically verify that Planar outperforms SOTA in memory and out-of-core systems in efficiency and scalability.