Office of Research, UC Riverside
Rajiv Gupta
Distinguished Professor
Computer Science & Engineering
rajivg@ucr.edu
(951) 827-2558


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

AWARD NUMBER
007582-002
FUND NUMBER
33159
STATUS
Active
AWARD TYPE
3-Grant
AWARD EXECUTION DATE
6/30/2015
BEGIN DATE
7/1/2015
END DATE
6/30/2018
AWARD AMOUNT
$400,000

Sponsor Information

SPONSOR AWARD NUMBER
1524852
SPONSOR
NATIONAL SCIENCE FOUNDATION
SPONSOR TYPE
Federal
FUNCTION
Organized Research
PROGRAM NAME

Proposal Information

PROPOSAL NUMBER
15070742
PROPOSAL TYPE
New
ACTIVITY TYPE
Basic Research

PI Information

PI
Gupta, Rajiv
PI TITLE
Other
PI DEPTARTMENT
Computer Science & Engineering
PI COLLEGE/SCHOOL
Bourns College of Engineering
CO PIs

Project Information

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.
(Abstract from NSF)