| Popis: |
In the last years researchers and industry have become interested in the analysis of graphs to gain insights into social networks, road networks, and other data that is naturally organized as a set of connected entities. Many of these graphs are very large, some containing hundreds of billions of edges. Usually, graphs are stored in static or immutable representations. We propose ASGraph. ASGraph is a graph container that supports updates and multi-versioning while still providing high analytical performance in the order of magnitude of the predominant CSR. ASGraph stores temporal graphs with arbitrarily fine granularity. Additionally, it can optimize its internal layout for analytical queries at specific snapshots. We show that it has moderate runtime overhead between 7% -- 98% for PageRank compared to CSR. Meanwhile it outperforms CSR both in runtime and memory consumption in scenarios where a graph is repeatedly updated between analysis. We designed ASGraph to support an update stream that can be applied concurrently to all analytical operations without blocking. In contrast to existing solutions for storing versioned graphs, its performance is independent of the number of stored snapshots. |
