.png){kind=icon}
.png){kind=icon}
Return
IncPregel: an incremental graph parallel computation model
.png){kind=icon}
PRE
AI
DOI：10.1007/s11704-016-6109-y.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
graph computation
Pregel
cloud computing
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4.6
Papers:
1.6K
Citations:
2.8K