TGDB: A System for Efficient Temporal Graph Analytics


Many real-world graphs appear as a massive temporal stream of edges and/or node updates. Examples include diverse types of interaction networks, such as communication activity in social graphs, vehicle and pedestrian traffic in road networks, molecular interaction in biological networks, and telemetry or provenance events in datacenter networks. These large-scale graphs present additional challenges for efficient graph query processing, such as heterogeneity (e.g., different types of nodes and edges in the same graph), as well as querying use cases that require support for analysis at multi-layer (e.g., different aggregation levels) and/or multi-view slices of the graph (e.g., wall posts vs likes on a Facebook social graph). To the extent of our knowledge, however, little work has focused on supporting efficient query processing on massive heterogeneous temporal networks. Furthermore, existing research in temporal network analysis has largely focused on graph algorithms for dynamic graphs, with little focus on efficient language and system support for multilayer and multi-view graph data processing and subgraph matching. To this end, we are designing and implementing a graph analytics system that supports primitives for efficient temporal analysis of large-scale networks. Our current focus is on data-structures – either novel ones, or extensions to the familiar CSR (Compressed Sparse Row) and LSM (Log-Structured Merge Trees) – that provide better cache locality for target temporal graph analytics workloads.

Participants

Joana M. F. da Trindade, Mengyuan Sun (MEng), Samuel Madden, Julian Shun