Optimizing Graph Algorithms on Pregel-like Systems

Summary: Graph algorithms on Pregel-like systems: tackle slow convergence and high comm costs from diameter and skew by combining vertex-centric parallelism with a tiny serial input portion. Open-source Pregel; experiments on large graphs show runtime gains. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10935
Venue: VLDB
Year: 2014
Pagerank: 9.0109891e-05
Overall Rank: 2,336 | 83.76%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Semih Salihoglu
2. Jennifer Widom

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,408	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012133511
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
2,754	Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing Systems	2015	VLDB	8.169411e-05
2,927	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.8823626e-05
4,234	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	6.3355073e-05
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
9,471	Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware	2025	SIGMOD	4.3341665e-05
9,613	Graft: A Debugging Tool For Apache Giraph	2015	SIGMOD	4.3177432e-05
10,525	Using Process Calculus for Optimizing Data and Computation Sharing in Complex Stateful Parallel Computations	2025	SIGMOD	4.1945683e-05
11,191	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,308	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012661651
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,709	Big Graph Analytics Systems	2016	SIGMOD	4.9529145e-05
1,685	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.0001091808
3,597	Parallel Local Graph Clustering	2016	VLDB	6.9345175e-05
4,845	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	5.8795333e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7392415e-05
1,408	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012133511
574	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019883211
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
2,927	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.8823626e-05
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923