Name
Abstract | ||
|---|---|---|
Large-scale graph computation is often required in a variety of emerging applications such as social network computation and Web services. Such graphs are typically large and frequently updated with minor changes. However, re-computing an entire graph when a few vertices or edges are updated is often prohibitively expensive. To reduce the cost of such updates, this study proposes an incremental graph computation model called IncPregel, which leverages the non-after-effect property of the first-order Markov chain and provides incremental programming abstractions to avoid redundant computation and message communication. This is accomplished by employing an efficient and fine-grained reuse mechanism. We implemented this model on Hama, a popular open source framework based on Pregel, to construct an incremental graph processing system called IncHama. IncHama automatically detects changes in input in order to recognize “changed vertices” and to exchange reusable data by means of shuffling. The evaluation results on large-scale graphs show that, compared with Hama, IncHama is 1.1–2.7 times faster and can reduce communication messages by more than 50% when the incremental edges increase in number from 0.1 to 100k. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.1007/s11704-016-6109-y | Frontiers Comput. Sci. |
Keywords | Field | DocType |
graph computation,Pregel,cloud computing | Social network,Vertex (geometry),Reuse,Computer science,Markov chain,Parallel computing,Shuffling,Web service,Cloud computing,Computation | Journal |
Volume | Issue | ISSN |
12 | 6 | 2095-2228 |
Citations | PageRank | References |
0 | 0.34 | 22 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Qiang Liu | 1 | 0 | 0.68 |
| Xiaoshe Dong | 2 | 172 | 51.44 |
| Heng Chen | 3 | 0 | 3.72 |
| Yinfeng Wang | 4 | 61 | 13.10 |