TY - JOUR

T1 - Automatic algorithm transformation for efficient multisnapshot analytics on temporal graphs

AU - Then, Manuel

AU - Kersten, Timo

AU - Günnemann, Stephan

AU - Kemper, Alfons

AU - Neumann, Thomas

N1 - Publisher Copyright:
© 2017 VLDB Endowment.

PY - 2017

Y1 - 2017

N2 - Analytical graph algorithms commonly compute metrics for a graph at one point in time. In practice it is often also of interest how metrics change over time, e.g., to find trends. For this purpose, algorithms must be executed for multiple graph snapshots. We present Single Algorithm Multiple Snapshots (SAMS), a novel approach to execute algorithms concurrently for multiple graph snapshots. SAMS automatically transforms graph algorithms to leverage similarities between the analyzed graph snapshots. The automatic transformation interleaves algorithm executions on multiple snapshots, synergistically shares their graph accesses and traversals, and optimizes the algorithm's data layout. Thus, SAMS can amortize the cost of random data accesses and improve memory bandwidth utilization-two main cost factors in graph analytics. We extensively evaluate SAMS using six well-known algorithms and multiple synthetic as well as real-world graph datasets. Our measurements show that in multi-snapshot analyses, SAMS offers runtime improvements of up to two orders of magnitude over traditional snapshot-at-a-time execution.

AB - Analytical graph algorithms commonly compute metrics for a graph at one point in time. In practice it is often also of interest how metrics change over time, e.g., to find trends. For this purpose, algorithms must be executed for multiple graph snapshots. We present Single Algorithm Multiple Snapshots (SAMS), a novel approach to execute algorithms concurrently for multiple graph snapshots. SAMS automatically transforms graph algorithms to leverage similarities between the analyzed graph snapshots. The automatic transformation interleaves algorithm executions on multiple snapshots, synergistically shares their graph accesses and traversals, and optimizes the algorithm's data layout. Thus, SAMS can amortize the cost of random data accesses and improve memory bandwidth utilization-two main cost factors in graph analytics. We extensively evaluate SAMS using six well-known algorithms and multiple synthetic as well as real-world graph datasets. Our measurements show that in multi-snapshot analyses, SAMS offers runtime improvements of up to two orders of magnitude over traditional snapshot-at-a-time execution.

UR - http://www.scopus.com/inward/record.url?scp=85026326301&partnerID=8YFLogxK

U2 - 10.14778/3090163.3090166

DO - 10.14778/3090163.3090166

M3 - Conference article

AN - SCOPUS:85026326301

SN - 2150-8097

VL - 10

SP - 877

EP - 888

JO - Proceedings of the VLDB Endowment

JF - Proceedings of the VLDB Endowment

IS - 8

T2 - 43rd International Conference on Very Large Data Bases, VLDB 2017

Y2 - 28 August 2017 through 1 September 2017

ER -