Automatic algorithm transformation for efficient multi-snapshot analytics on temporal graphs
| Autor: | Manuel Then, Alfons Kemper, Timo Kersten, Stephan Günnemann, Thomas Neumann |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
SPQR tree
Theoretical computer science Graph database Computer science business.industry General Engineering 02 engineering and technology computer.software_genre Graph Analytics 020204 information systems 0202 electrical engineering electronic engineering information engineering Leverage (statistics) Snapshot (computer storage) 020201 artificial intelligence & image processing business computer |
| Zdroj: | Proceedings of the VLDB Endowment. 10:877-888 |
| ISSN: | 2150-8097 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|