EIGA: elastic and scalable dynamic graph analysis

Modern graphs are not only large, but rapidly changing. The rate of change can vary significantly along with the computational cost. Existing distributed graph analysis systems have largely been designed to operate on static graphs. Infrastructure changes in these systems need to occur when the system is idle, which can result in significant wasted resources or the inability to cope with changes.

We present ElGA, an elastic and scalable dynamic graph analysis system. Using a shared-nothing architecture and consistent hashing, ElGA can scale elastically as the graph grows or more computation is required. By applying sketches, we perform an edge partitioning of the graph where high degree vertices can be split among multiple nodes. ElGA supports both synchronous and asynchronous vertex-centric applications that operate in batches on a continuously changing graph.

We experimentally demonstrate that ElGA outperforms stateof-the-art static systems while supporting client queries, elastic infrastructure changes, and dynamic algorithms.