TeGraph plus : Scalable Temporal Graph Processing Enabling Flexible Edge Modifications

Chengying Huan

doi:10.1109/TPDS.2024.3393914

2024-08-01

PRE

DOI：10.1109/TPDS.2024.3393914

原文链接

原文求助

摘要

En 中文

Temporal graphs are widely used for time-critical applications, which enable the extraction of graph structural information with temporal features but cannot be efficiently supported by static graph computing systems. However, the current state-of-the-art solutions for temporal graph problems are not only ad-hoc and suboptimal, but they also exhibit poor scalability, particularly in terms of their inability to scale to evolving graphs with flexible edge modifications (including insertions and deletions) and diverse execution environments. In this article, we present two key observations. First, temporal path problems can be characterized as topological-optimum problems, which can be efficiently resolved using a universal single-scan execution model. Second, data redundancy in transformed temporal graphs can be mitigated by merging superfluous vertices. Building upon these fundamental insights, we propose TeGraph+, a versatile temporal graph computing engine that makes the following contributions: (1) a unified optimization strategy and execution model for temporal graph problems; (2) a novel graph transformation model with graph redundancy reduction strategy; (3) a spanning tree decomposition (STD) based distributed execution model which uses an efficient transformed graph decomposition strategy to partition the transformed graph into different spanning trees for distributed execution; (4) an efficient mixed imperative and lazy graph update strategy that offers support for evolving graphs with flexible edge modifications; (5) a general system framework with user-friendly APIs and the support of various execution environments, including in-memory, out-of-core, and distributed execution environments. Our extensive evaluation reveals that TeGraph+ can achieve up to 241x speedups over the state-of-the-art counterparts.

Keyword:

Time factors

Computational modeling

Scalability

Engines

Bandwidth

Heuristic algorithms

Data models

Graph algorithm

temporal graphs

parallel and distributed system