PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

Joseph E. GonzalezYucheng LowHaijie GuDanny BicksonCarlos Guestrin

article2012OSDI2,028 citations

Carnegie Mellon University University of Washington bipartite graphs parallel computation graph-parallel computation PowerGraph abstraction natural graphs

jegonzal/PowerGraph Gonzalez et al (2012).pdf

Paper: Pregel: a system for large-scale graph processing, Grzegorz Malewicz et al. (2010). Pregel introduced the bulk-synchronous vertex-centric programming abstraction that PowerGraph directly analyzes and refactors into the Gather-Apply-Scatter model to handle power-law degree distributions.

No sufficiently relevant recommendations were found.

Cover for PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

Abstract

Large-scale graph-structured computation is central to tasks ranging from targeted advertising to natural language processing and has led to the development of several graph-parallel abstractions including Pregel and GraphLab. However, the natural graphs commonly found in the real-world have highly skewed power-law degree distributions, which challenge the assumptions made by these abstractions, limiting performance and scalability.

In this paper, we characterize the challenges of computation on natural graphs in the context of existing graph-parallel abstractions. We then introduce the PowerGraph abstraction which exploits the internal structure of graph programs to address these challenges. Leveraging the PowerGraph abstraction we introduce a new approach to distributed graph placement and representation that exploits the structure of power-law graphs. We provide a detailed analysis and experimental evaluation comparing PowerGraph to two popular graph-parallel systems. Finally, we describe three different implementation strategies for PowerGraph and discuss their relative merits with empirical evaluations on large-scale real-world problems demonstrating order of magnitude gains.

Topics

bipartite graphs parallel computation

Keywords

graph-parallel computation PowerGraph abstraction natural graphs power-law graphs vertex programs vertex cuts hypergraph partitioning graph placement asynchronous computation graph coloring

1 Introduction
2 Graph-Parallel Abstractions
2.1 Pregel
2.2 GraphLab
2.3 Characterization
3 Challenges of Natural Graphs
4 PowerGraph Abstraction
4.1 GAS Vertex-Programs
4.2 Delta Caching
4.3 Initiating Future Computation
4.3.1 Bulk Synchronous Execution
4.3.2 Asynchronous Execution
4.4 Comparison with GraphLab / Pregel
5 Distributed Graph Placement
5.1 Balanced p-way Vertex-Cut
5.2 Greedy Vertex-Cuts
6 Abstraction Comparison
6.1 Computation Imbalance
6.2 Communication Imbalance
6.3 Runtime Comparison
7 Implementation and Evaluation
7.1 Graph Loading and Placement
7.2 Synchronous Engine (Sync)
7.3 Asynchronous Engine (Async)
7.4 Async. Serializable Engine (Async+S)
7.5 Fault Tolerance
7.6 MLDM Applications
8 Related Work
9 Conclusions and Future Work
Acknowledgments
References

Knowls

Knowl 1 — GAS (Gather, Apply, Scatter) Model of Graph Computation
model/method
The Gather-Apply-Scatter (GAS) model decomposes graph-parallel vertex-programs into three distinct conceptual phases executed on a graph $G = (V, E)$ where each vertex $v \in V$ stores data $D_v$ and each edge $(u,v) \in E$ stores data $D_{(u,v)}$ :
1. Gather: Information about adjacent vertices and edges is collected through a user-defined function $g$ and aggregated over the neighborhood $\text{Nbr}[u]$ of vertex $u$ using a user-defined commutative and associative binary operator $\oplus$ : $\Sigma \leftarrow \bigoplus_{v \in \text{Nbr}[u]} g(D_u, D_{(u,v)}, D_v)$
2. Apply: The aggregated accumulator value $\Sigma$ is used to compute an updated value for the center vertex $u$ : $D_u^{\text{new}} \leftarrow a(D_u, \Sigma)$
3. Scatter: The updated vertex value $D_u^{\text{new}}$ is used to update data on adjacent edges: $\forall v \in \text{Nbr}[u] : D_{(u,v)} \leftarrow s(D_u^{\text{new}}, D_{(u,v)}, D_v)$
The gather and scatter phases can independently restrict their neighborhood $\text{Nbr}[u]$ to incoming edges (IN_NBRS), outgoing edges (OUT_NBRS), all adjacent edges (ALL_NBRS), or no edges (NO_NBRS).
Knowl 2 — PowerGraph Factored Vertex-Program Execution Algorithm
algorithm
PowerGraph executes vertex-programs by factoring the gather, apply, and scatter functions over edges, allowing the computation of a single high-degree vertex to be distributed across multiple worker machines.
Input: Center vertex $u$ , graph state with vertex data $D$ and edge data $D_{(\cdot,\cdot)}$
if cached accumulator $a_u$ is empty then
    for each neighbor $v$ in gather_nbrs( $u$ ) do
         $a_u \leftarrow \text{sum}(a_u, \text{gather}(D_u, D_{(u,v)}, D_v))$
    end for
end if
$D_u \leftarrow \text{apply}(D_u, a_u)$
for each neighbor $v$ in scatter_nbrs( $u$ ) do
     $(D_{(u,v)}, \Delta a) \leftarrow \text{scatter}(D_u, D_{(u,v)}, D_v)$
    if $a_v \neq \text{Empty}$ and $\Delta a \neq \text{Empty}$ then
         $a_v \leftarrow \text{sum}(a_v, \Delta a)$
    else
         $a_v \leftarrow \text{Empty}$
    end if
end for
The gather and scatter functions execute in parallel across all edges adjacent to $u$ on the machines hosting those edges. The apply function is executed by the master replica of vertex $u$ , which atomically writes $D_u^{\text{new}}$ back to the graph and synchronizes the updated state to all mirror replicas.
Knowl 3 — Balanced p-Way Vertex-Cut Distributed Graph Placement
model/method
In a balanced $p$ -way vertex-cut, each edge $e \in E$ of a graph $G = (V, E)$ is assigned to exactly one machine $A(e) \in \{1, \dots, p\}$ . A vertex $v$ spans the set of machines $A(v) = \{A(e) \mid e \text{ is incident to } v\}$ . The number of replicas of vertex $v$ across the cluster is $|A(v)|$ .

The balanced $p$ -way vertex-cut optimization problem is formulated as: $\min_A \frac{1}{|V|} \sum_{v \in V} |A(v)|$ $\text{subject to } \max_{m \in \{1, \dots, p\}} |\{e \in E \mid A(e) = m\}| \le \lambda \frac{|E|}{p}$ where $\lambda \ge 1$ is a constant imbalance factor.

For each vertex $v$ with $|A(v)| > 1$ , one replica is designated as the master replica, which maintains the authoritative vertex data and executes the apply phase. All other $|A(v)| - 1$ replicas act as mirrors holding local cached read-only copies of $D_v$ . Edge data $D_{(u,v)}$ is stored on exactly one machine without replication, eliminating network synchronization of edge state.
Knowl 4 — Greedy Vertex-Cut Edge Placement Algorithm
algorithm
The greedy vertex-cut placement algorithm de-randomizes edge assignment by sequentially placing each incoming edge on the machine that minimizes the conditional expected replication factor.
Input: Edge $e = (u, v)$ to assign, current machine sets $A(u)$ and $A(v)$ , machine loads $L(m)$ for $m \in \{1, \dots, p\}
Output: Machine assignment $k \in \{1, \dots, p\}
if $A(u) \cap A(v) \neq \emptyset$ then
     $k \leftarrow \arg\min_{m \in A(u) \cap A(v)} L(m)$
else if $A(u) \neq \emptyset$ and $A(v) \neq \emptyset$ then
    Let $w \in \{u, v\}$ be the vertex with more unassigned edges
     $k \leftarrow \arg\min_{m \in A(w)} L(m)$
else if $A(u) \neq \emptyset$ or $A(v) \neq \emptyset$ then
    Let $w \in \{u, v\}$ be the assigned vertex
     $k \leftarrow \arg\min_{m \in A(w)} L(m)$
else
     $k \leftarrow \arg\min_{m \in \{1, \dots, p\}} L(m)$
end if
$A(u) \leftarrow A(u) \cup \{k\}$
$A(v) \leftarrow A(v) \cup \{k\}$
$L(k) \leftarrow L(k) + 1$
return $k$
PowerGraph implements this heuristic in two distributed configurations:
1. Coordinated: Machine assignments $A(v)$ are maintained in a globally distributed table with local caching.
2. Oblivious: Each worker machine runs the greedy heuristic independently using only local history, requiring zero inter-machine communication during graph loading.
Knowl 5 — Expected Vertex Replication for Randomized Vertex-Cuts in Power-Law Graphs
theoretical result
When edges of a graph $G = (V,E)$ are assigned uniformly at random to $p$ machines, the expected normalized vertex replication factor is: $\mathbb{E}\left[\frac{1}{|V|} \sum_{v \in V} |A(v)|\right] = \frac{p}{|V|} \sum_{v \in V} \left(1 - \left(1 - \frac{1}{p}\right)^{D[v]}\right)$ where $D[v]$ is the degree of vertex $v$ , and $A(v)$ is the set of machines holding edges incident to $v$ .

For a graph whose degree distribution follows a power-law Zipf distribution $P(d) = d^{-\alpha} / h_{|V|}(\alpha)$ for $d \in \{1, \dots, |V|-1\}$ with exponent $\alpha > 0$ and normalizing constant $h_{|V|}(\alpha) = \sum_{d=1}^{|V|-1} d^{-\alpha}$ , the expected normalized replication factor is: $\mathbb{E}\left[\frac{1}{|V|} \sum_{v \in V} |A(v)|\right] = p - \frac{p}{h_{|V|}(\alpha)} \sum_{d=1}^{|V|-1} \left(\frac{p-1}{p}\right)^d d^{-\alpha}$
Knowl 6 — Delta Caching for Gather State Maintenance
model/method
Delta caching dynamically maintains the gather accumulator result across iterations to avoid re-executing gather on unchanged neighbors.

The execution engine caches the accumulator $a_u$ from the previous gather phase for each vertex $u$ . During the scatter phase on edge $(u,v)$ , the user-defined scatter function can return an additive correction term $\Delta a$ . When the accumulator domain forms an abelian group with commutative and associative addition $(+)$ and an inverse $(-)$ , the change is computed as: $\Delta a = g(D_u^{\text{new}}, D_{(u,v)}^{\text{new}}, D_v^{\text{new}}) - g(D_u, D_{(u,v)}, D_v)$ where $g$ is the gather function.

The delta $\Delta a$ is atomically added to the neighbor's cached accumulator using $a_v \leftarrow \text{sum}(a_v, \Delta a)$ . When vertex $v$ subsequently executes, it reuses $a_v$ and skips the gather phase entirely. If scatter returns no delta ( $ext{NULL}$ ), $a_v$ is cleared, forcing a full gather on $v$ 's next execution.
Knowl 7 — Distributed Serializability via Chandy-Misra on Vertex-Cuts
model/method
PowerGraph's Asynchronous Serializable (Async+S) engine guarantees serializability (preventing adjacent vertex-programs from executing concurrently) by adapting the Chandy-Misra dining philosophers algorithm to vertex-cuts.

In this scheme, each vertex corresponds to a philosopher and each edge corresponds to a fork:
1. Rather than acquiring locks sequentially, each replica of vertex $v$ across machines $A(v)$ requests forks in parallel for only its locally hosted edges.
2. The master replica coordinates with mirror replicas via a consensus protocol to determine when all replicas have successfully acquired all incident local forks.
3. Once consensus is established, the vertex-program executes across the master and mirrors.
4. When execution finishes, the acquired forks are released to satisfy competing neighbor requests.
This parallel locking protocol avoids the contention bottlenecks and starvation that sequential ordering protocols experience on high-degree vertices in power-law graphs.
Knowl 8 — Mirror Bound of Vertex-Cuts Relative to Edge-Cut Ghosts
theoretical result
For any graph $G = (V, E)$ partitioned across machines, an edge-cut partitioning that induces $g$ ghost vertices (replicated vertex states on remote machines required to represent cut edges) can be converted along the same partition boundary into a vertex-cut that has strictly fewer than $g$ mirror replicas.

Specifically, for a two-way edge cut crossing edge set $E' \subseteq E$ whose incident vertex set is $V' \subseteq V$ , the edge-cut creates $|V'|$ ghosts, whereas the corresponding vertex-cut creates at most $|V'| - 1$ mirrors.
Knowl 9 — Expected Edge-Cut Fraction for Random Vertex Partitioning
theoretical result
When vertices of a graph $G = (V,E)$ are assigned uniformly at random to $p$ machines (random edge-cut placement), the expected fraction of cut edges spanning different machines is: $\mathbb{E}\left[\frac{|\text{Edges Cut}|}{|E|}\right] = 1 - \frac{1}{p}$

For a power-law degree distribution with exponent $\alpha$ and Zipf normalizing constant $h_{|V|}(\alpha) = \sum_{d=1}^{|V|-1} d^{-\alpha}$ , the expected number of cut edges per vertex is: $\mathbb{E}\left[\frac{|\text{Edges Cut}|}{|V|}\right] = \left(1 - \frac{1}{p}\right) \mathbb{E}[D[v]] = \left(1 - \frac{1}{p}\right) \frac{h_{|V|}(\alpha - 1)}{h_{|V|}(\alpha)}$ where $D[v]$ is the degree of vertex $v$ .

Knowl 10 — Performance of PowerGraph Against Distributed Baselines on MLDM Tasks

data/table

Application / System	Metric / Runtime	$\|V\|$	$\|E\|$	Cluster Config (Nodes $\times$ Cores)
PageRank (per iteration)
Hadoop	198 s	–	1.1 B	$50 \times 8$
Spark	97.4 s	40 M	1.5 B	$50 \times 2$
Twister	36 s	50 M	1.4 B	$64 \times 4$
PowerGraph (Sync)	3.6 s	40 M	1.5 B	$64 \times 8$
Triangle Count (total runtime)
Hadoop	423 min	40 M	1.4 B	$1636 \times ?$
PowerGraph (Sync)	1.5 min	40 M	1.4 B	$64 \times 16$
LDA (tokens per second)
Smola et al.	150 M tok/s	1000 topics	–	$100 \times 8$
PowerGraph (Async)	110 M tok/s	1000 topics	–	$64 \times 16$

This benchmark demonstrates PowerGraph's execution performance on large real-world graphs (Twitter follower network with ${\approx}40\text{M}$ vertices and $1.4\text{B}$ -- $1.5\text{B}$ edges, and Wikipedia term-document graph for Latent Dirichlet Allocation). On PageRank, PowerGraph Synchronous computes one iteration in 3.6 seconds on 64 nodes (512 cores), which is $27\times$ faster than Spark ( $97.4\text{ s}$ on 100 cores) and $55\times$ faster than Hadoop. On Triangle Counting, PowerGraph Synchronous finishes in 1.5 minutes on 64 nodes (1024 virtual cores), compared to 423 minutes for Hadoop on a 1636-node cluster. On LDA with 1000 topics, PowerGraph Asynchronous reaches 110 million tokens/second using 200 lines of user code, approaching the 150 million tokens/second achieved by a specialized LDA architecture on 100 nodes.

Knowl 11 — Work Balance and Communication Invariance of PowerGraph Across Power-Law Exponents
empirical result
Across 10-million vertex synthetic power-law graphs with exponents $\alpha \in [1.8, 2.2]$ on an 8-node cluster (64 worker threads):
- Work Imbalance: Pregel (Piccolo) exhibits severe work imbalance on power-law fan-out graphs (per-iteration worker runtime standard deviation rising from $\approx 5$ to $> 45$ as $\alpha$ decreases to 1.8), while GraphLab exhibits severe imbalance on power-law fan-in graphs (standard deviation rising from $\approx 5$ to $> 25$ ). PowerGraph maintains a constant, low standard deviation ( $\le 5$ ) regardless of $\alpha$ or edge direction due to edge factoring.
- Communication Volume: PowerGraph communicates significantly fewer bytes per iteration ( ${\approx} 2\text{ GB}$ at $\alpha=1.8$ ) compared to GraphLab ( ${\approx} 6.5\text{ GB}$ ) and Pregel ( ${\approx} 8\text{ GB}$ on fan-out), with communication volume remaining nearly invariant to power-law fan-in versus fan-out skew.
Knowl 12 — Empirical Impact of Vertex-Cut Partitioning Heuristics on Replication and Execution Time
empirical result
Evaluated on 32 Amazon EC2 cc1.4xlarge instances across five real-world graphs (Twitter with 41M vertices / 1.4B edges, UK web graph with 132.8M vertices / 5.5B edges, Amazon, LiveJournal, and Hollywood):
- Replication Factor: Greedy coordinated and oblivious vertex-cut heuristics reduce the replication factor from 15–18 (random vertex-cut) down to 2–4 on the Twitter graph.
- Runtime Scaling: Application execution time scales linearly with the replication factor; halving the replication factor approximately halves runtime across PageRank, SSSP, Graph Coloring, and ALS.
- Ingress Overhead: On the Twitter graph over 64 machines, graph ingress times are 59 seconds for random, 105 seconds for oblivious, and 239 seconds for coordinated placement. Oblivious partitioning achieves replication factors within 10%–20% of coordinated partitioning while avoiding the network communication overhead of a distributed assignment table.

Coverage note — None omitted; all core contributions—including theoretical formulations, algorithms, execution engines, and empirical evaluations—have been captured as self-contained knowls.

References

1.ABOU-RJEILI, A., AND KARYPIS, G. Multilevel algorithms for partitioning power-law graphs. In IPDPS (2006).
2.AHMED, A., ALY, M., GONZALEZ, J., NARAYANAMURTHY, S., AND SMOLA, A. J. Scalable inference in latent variable models. In WSDM (2012), pp. 123–132.
3.ALBERT, R., JEONG, H., AND BARABÁSI, A. L. Error and attack tolerance of complex networks. In Nature (2000), vol. 406, pp. 378—482.
4.BERTSEKAS, D. P., AND TSITSIKLIS, J. N. Parallel and distributed computation: numerical methods. Prentice-Hall, 1989.
5.BOLDI, P., ROSA, M., SANTINI, M., AND VIGNA, S. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In WWW (2011), pp. 587–596.
6.BOLDI, P., AND VIGNA, S. The WebGraph framework I: Compression techniques. In WWW (2004), pp. 595–601.
7.BORDINO, I., BOLDI, P., DONATO, D., SANTINI, M., AND VIGNA, S. Temporal evolution of the uk web. In ICDM Workshops (2008), pp. 909–918.
8.BULUÇ, A., AND GILBERT, J. R. The combinatorial blas: design, implementation, and applications. IJHPCA 25, 4 (2011), 496–509.
9.CATALYUREK, U., AND AYKANAT, C. Decomposing irregularly sparse matrices for parallel matrix-vector multiplication. In IRREGULAR (1996), pp. 75–86.
10.CHANDY, K. M., AND MISRA, J. The drinking philosophers problem. ACM Trans. Program. Lang. Syst. 6, 4 (Oct. 1984), 632–646.
11.CHENG, R., HONG, J., KYROLA, A., MIAO, Y., WENG, X., WU, M., YANG, F., ZHOU, L., ZHAO, F., AND CHEN, E. Kineograph: taking the pulse of a fast-changing and connected world. In EuroSys (2012), pp. 85–98.
12.CHIERICHETTI, F., KUMAR, R., LATTANZI, S., MITZENMACHER, M., PANCONESI, A., AND RAGHAVAN, P. On compressing social networks. In KDD (2009), pp. 219–228.
13.DEVINE, K. D., BOMAN, E. G., HEAPHY, R. T., BISSELING, R. H., AND CATALYUREK, U. V. Parallel hypergraph partitioning for scientific computing. In IPDPS (2006).
14.DIJKSTRA, E. W. Hierarchical ordering of sequential processes. Acta Informatica 1 (1971), 115–138.
15.EKANAYAKE, J., LI, H., ZHANG, B., GUNARATHNE, T., BAE, S., QIU, J., AND FOX, G. Twister: A runtime for iterative MapReduce. In HPDC (2010), ACM.
16.FALOUTSOS, M., FALOUTSOS, P., AND FALOUTSOS, C. On power-law relationships of the internet topology. ACM SIGCOMM Computer Communication Review 29, 4 (1999), 251–262.
17.GONZALEZ, J., LOW, Y., GRETTON, A., AND GUESTRIN, C. Parallel gibbs sampling: From colored fields to thin junction trees. In AISTATS (2011), vol. 15, pp. 324–332.
18.GONZALEZ, J., LOW, Y., AND GUESTRIN, C. Residual splash for optimally parallelizing belief propagation. In AISTATS (2009), vol. 5, pp. 177–184.
19.GONZALEZ, J., LOW, Y., GUESTRIN, C., AND O’HALLARON, D. Distributed parallel inference on large factor graphs. In UAI (2009).
20.GREGOR, D., AND LUMSDAINE, A. The parallel BGL: A generic library for distributed graph computations. POOSC (2005).
21.HOFMANN, T. Probabilistic latent semantic indexing. In SIGIR (1999), pp. 50–57.
22.KANG, U., TSOURAKAKIS, C. E., AND FALOUTSOS, C. Pegasus: A peta-scale graph mining system implementation and observations. In ICDM (2009), pp. 229 –238.
23.KARYPIS, G., AND KUMAR, V. Multilevel k-way partitioning scheme for irregular graphs. J. Parallel Distrib. Comput. 48, 1 (1998), 96–129.
24.KWAK, H., LEE, C., PARK, H., AND MOON, S. What is twitter, a social network or a news media? In WWW (2010), pp. 591–600.
25.KYROLA, A., BLELLOCH, G., AND GUESTRIN, C. GraphChi: Large-scale graph computation on just a PC. In OSDI (2012).
26.LANG, K. Finding good nearly balanced cuts in power law graphs. Tech. Rep. YRL-2004-036, Yahoo! Research Labs, Nov. 2004.
27.LESKOVEC, J., KLEINBERG, J., AND FALOUTSOS, C. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data 1, 1 (mar 2007).
28.LESKOVEC, J., LANG, K. J., DASGUPTA, A., , AND MAHONEY, M. W. Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics 6, 1 (2008), 29–123.
29.LOW, Y., GONZALEZ, J., KYROLA, A., BICKSON, D., GUESTRIN, C., AND HELLERSTEIN, J. M. Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud. PVLDB (2012).
30.MALEWICZ, G., AUSTERN, M. H., BIK, A. J., DEHNERT, J., HORN, I., LEISER, N., AND CZAJKOWSKI, G. Pregel: a system for large-scale graph processing. In SIGMOD (2010).
31.PELLEGRINI, F., AND ROMAN, J. Scotch: A software package for static mapping by dual recursive bipartitioning of process and architecture graphs. In HPCN Europe (1996), pp. 493–498.
32.POWER, R., AND LI, J. Piccolo: building fast, distributed programs with partitioned tables. In OSDI (2010).
33.PUJOL, J. M., ERRAMILLI, V., SIGANOS, G., YANG, X., LAOUTARIS, N., CHHABRA, P., AND RODRIGUEZ, P. The little engine(s) that could: scaling online social networks. In SIGCOMM (2010), pp. 375–386.
34.SMOLA, A. J., AND NARAYANAMURTHY, S. An Architecture for Parallel Topic Models. PVLDB 3, 1 (2010), 703–710.
35.STANTON, I., AND KLIOT, G. Streaming graph partitioning for large distributed graphs. Tech. Rep. MSR-TR-2011-121, Microsoft Research, November 2011.
36.SURI, S., AND VASSILVITSKII, S. Counting triangles and the curse of the last reducer. In WWW (2011), pp. 607–614.
37.ZAHARIA, M., CHOWDHURY, M., FRANKLIN, M. J., SHENKER, S., AND STOICA, I. Spark: Cluster computing with working sets. In HotCloud (2010).
38.ZHOU, Y., WILKINSON, D., SCHREIBER, R., AND PAN, R. Large-scale parallel collaborative filtering for the netflix prize. In AAIM (2008), pp. 337–348.

Citation

MLA

Gonzalez, J. E., et al. “PowerGraph: Distributed Graph-parallel Computation on Natural Graphs”. Operating Systems Design and Implementation, 2012, pp. 17–30, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7712.

APA

Gonzalez, J. E., Low, Y., Gu, H., Bickson, D., & Guestrin, C. (2012). PowerGraph: distributed graph-parallel computation on natural graphs. Operating Systems Design and Implementation, 17–30. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7712

Chicago

Gonzalez, J. E., Y. Low, H. Gu, D. Bickson, and C. Guestrin. 2012. “PowerGraph: Distributed Graph-parallel Computation on Natural Graphs”. Operating Systems Design and Implementation, 17–30. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7712.

Harvard

Gonzalez, J.E. et al. (2012) “PowerGraph: distributed graph-parallel computation on natural graphs”, Operating Systems Design and Implementation, pp. 17–30. Available at: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7712.

Vancouver

1. Gonzalez JE, Low Y, Gu H, Bickson D, Guestrin C (2012) PowerGraph: distributed graph-parallel computation on natural graphs. Operating Systems Design and Implementation 17–30

BibTeX

@article{gonzalez2012powergraph,
  title = {PowerGraph: distributed graph-parallel computation on natural graphs},
  author = {Gonzalez, Joseph E. and Low, Yucheng and Gu, Haijie and Bickson, Danny and Guestrin, Carlos},
  year = {2012},
  journal = {Operating Systems Design and Implementation},
  pages = {17-30},
  url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.258.7712}
}

Metadata:DOI registry

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — GAS (Gather, Apply, Scatter) Model of Graph Computation

Knowl 2 — PowerGraph Factored Vertex-Program Execution Algorithm

Knowl 3 — Balanced p-Way Vertex-Cut Distributed Graph Placement

Knowl 4 — Greedy Vertex-Cut Edge Placement Algorithm

Knowl 5 — Expected Vertex Replication for Randomized Vertex-Cuts in Power-Law Graphs

Knowl 6 — Delta Caching for Gather State Maintenance

Knowl 7 — Distributed Serializability via Chandy-Misra on Vertex-Cuts

Knowl 8 — Mirror Bound of Vertex-Cuts Relative to Edge-Cut Ghosts

Knowl 9 — Expected Edge-Cut Fraction for Random Vertex Partitioning