SHF: Small: Transformations for Synergistic Analysis of Large Evolving Graphs

University Of California-Riverside, Riverside CA

Investigators

Abstract

The importance of graph processing has grown with the popularity of graph analytics. An important feature of real-world graphs is that they are constantly evolving (e.g., social networks, networks modeling spreading of a disease etc.). Graph analytics over an evolving graph entails repeating analysis over snapshots of a graph taken at different points in time to observe how features of interest change over time. For large real-world graphs with tens of billions of edges, evolving graph analysis is both highly compute- and memory-intensive. By developing transformations that reorganize the computation and data, techniques for rapid evolving graph analytics on modern computing platforms are being considered. Many students are being trained and educated in this important field. Graph analysis can greatly benefit from cores and storage available on modern parallel machines. However, effectively exploiting the resources remains an enormous challenge due to irregular nature of parallelism and lack of data locality in graph computations. This work is leveraging two key characteristics, overlapping working sets and computed value stability, to develop techniques for speeding up graph analytics. The techniques being considered include: optimization of reading and writing of large graphs on disk, optimizing inter-node communication on a cluster, and optimizing computation over multiple versions of an evolving graph. These optimizations are being used to greatly enhance the performance of multiple popular graph processing systems. Public dissemination of these software enhancements are also planned.