Towards memory-efficient incremental processing of streaming graphs

With growing interest in efficiently analyzing dynamic graphs, streaming graph processing systems rely on stateful iterative models where they track the intermediate state as execution progresses in order to incrementally adjust the results upon graph mutation to reflect the changes in the latest version of the graph. We observe that the intermediate state tracked by these stateful iterative models significantly increases the memory footprint of these systems, which limits their scalability on large graphs. Due to the ever-increasing size of real-world graphs, it is crucial to develop solutions that actively limit their memory footprint while still delivering the benefits of incremental processing. We develop memory-efficient stateful iterative models that demand much less memory capacity to efficiently process streaming graphs with delivering the same results as provided by existing stateful iterative models. First, we propose a Selective Stateful Iterative Model where the memory footprint is controlled by selecting a small portion of the intermediate state to be maintained throughout execution, and the selection can be configured based on the capacity of the system's memory. Then, we propose a Minimal Stateful Iterative Model that further reduces the memory footprint by exploiting the key properties of graph algorithms. We develop incremental processing strategies for both of our models in order to correctly compute the effects of graph mutations on the final results even when intermediate states are not available. The evaluation shows our memory-efficient models are effective in limiting the memory footprint while still retaining most of the performance benefits of traditional stateful iterative models, hence being able to scale on larger graphs that could not be handled by the traditional models.