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: 10936
Venue: VLDB
Year: 2014
Pagerank: 9.0173968e-05
Overall Rank: 2,332 | 83.80%
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,410	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012127229
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
2,761	Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing Systems	2015	VLDB	8.1616217e-05
2,916	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.9062736e-05
4,236	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	6.3296839e-05
4,726	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.9632682e-05
9,473	Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware	2025	SIGMOD	4.3300131e-05
9,613	Graft: A Debugging Tool For Apache Giraph	2015	SIGMOD	4.3136057e-05
10,534	Using Process Calculus for Optimizing Data and Computation Sharing in Complex Stateful Parallel Computations	2025	SIGMOD	4.1905499e-05
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-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.0019040811
1,114	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013871948
1,312	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00012650678
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
6,706	Big Graph Analytics Systems	2016	SIGMOD	4.9501419e-05
1,684	Fast Iterative Graph Computation with Block Updates	2013	VLDB	0.00010912102
3,600	Parallel Local Graph Clustering	2016	VLDB	6.9285467e-05
4,845	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD	5.8731048e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7346959e-05
1,410	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012127229
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
2,916	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.9062736e-05
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811