ImmortalGraph
Citations Over TimeTop 10% of 2015 papers
Abstract
Temporal graphs that capture graph changes over time are attracting increasing interest from research communities, for functions such as understanding temporal characteristics of social interactions on a time-evolving social graph. ImmortalGraph is a storage and execution engine designed and optimized specifically for temporal graphs. Locality is at the center of ImmortalGraph’s design: temporal graphs are carefully laid out in both persistent storage and memory, taking into account data locality in both time and graph-structure dimensions. ImmortalGraph introduces the notion of locality-aware batch scheduling in computation, so that common “bulk” operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of ImmortalGraph explores an interesting interplay among locality, parallelism, and incremental computation in supporting common mining tasks on temporal graphs. The result is a high-performance temporal-graph system that is up to 5 times more efficient than existing database solutions for graph queries. The locality optimizations in ImmortalGraph offer up to an order of magnitude speedup for temporal iterative graph mining compared to a straightforward application of existing graph engines on a series of snapshots.
Related Papers
- → Temporal locality and its impact on Web proxy cache performance(2000)83 cited
- → Comparison of speedups for computing π using .NET TPL and OpenMP parallelization techonologies(2014)2 cited
- → BEAST: A Buffer Replacement Algorithm Using Spatial and Temporal Locality(2006)1 cited
- → Image processing in airborne applications using multicore embedded computers(2013)