Chronos
Wentao Han, Youshan Miao, Kaiwei Li et al. · European Conference on Computer Systems · 2014
Temporal graphs capture changes in graphs over time and are becoming a subject that attracts increasing interest from the research communities, for example, to understand temporal characteristics of social interactions on a time-evolving social graph. Chronos is a storage and execution engine designed and optimized specifically for running in-memory iterative graph computation on temporal graphs. Locality is at the center of the Chronos design, where the in-memory layout of temporal graphs and the scheduling of the iterative computation on temporal graphs are carefully designed, so that common "bulk" operations on temporal graphs are scheduled to maximize the benefit of in-memory data locality. The design of Chronos further explores the 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 offers 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.
Cited by 161 works. doi:10.1145/2592798.2592799
Authors
- Wentao Han
- Youshan Miao
- Kaiwei Li
- Ming Wu
- Fan Yang
- Lidong Zhou
- Vijayan Prabhakaran
- Wenguang Chen
- Enhong Chen
References
- The anatomy of a large-scale hypertextual Web search engine
- Resilient distributed datasets: a fault-tolerant abstraction for in-memory cluster computing
- Pregel
- Graphs over time
- Distributed GraphLab
- User interactions in social networks and their implications
- PowerGraph: distributed graph-parallel computation on natural graphs
- Differences in the mechanics of information diffusion across topics
- Cache-oblivious algorithms
- Naiad