Publication
ICDE 2021
Conference paper

Trillion-scale graph processing simulation based on top-down graph upscaling

View publication

Abstract

As the number of graph applications increases rapidly in many domains, new graph algorithms (or queries) have become more important than ever before. The current two-step approach to develop and test a graph algorithm is very expensive for trillion-scale graphs required in many industrial applications. In this paper, we propose a concept of graph processing simulation, a single-step approach that generates a graph and processes a graph algorithm simultaneously. It consists of a top-down graph upscaling method called V-Upscaler and a graph processing simulation method following the vertex-centric GAS model called T-GPS. Users can develop a graph algorithm and check its correctness and performance conveniently and cost-efficiently even for trillion-scale graphs. Through extensive experiments, we have demonstrated that our single-step approach of V-Upscaler and T-GPS significantly outperforms the conventional two-step approach, although ours uses only a single machine, while the conventional one uses a cluster of eleven machines.

Date

Publication

ICDE 2021

Authors

Share