ImmortalGraph
Authors:
Open Access
- 24 July 2015
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Storage
- Vol. 11 (3) , 1-34
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.Keywords
This publication has 24 references indexed in Scilit:
- X-Stream2013
- Presto2013
- Mizan2013
- Kineograph2012
- Distributed GraphLabProceedings of the VLDB Endowment, 2012
- The HV-treeProceedings of the VLDB Endowment, 2010
- A large time-aware web graphACM SIGIR Forum, 2008
- On Dynamic Shortest Paths ProblemsLecture Notes in Computer Science, 2004
- Comparison of access methods for time-evolving dataACM Computing Surveys, 1999
- The anatomy of a large-scale hypertextual Web search engineComputer Networks and ISDN Systems, 1998