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: 11123
Venue: VLDB
Year: 2014
Pagerank: 8.7932254e-05
Overall Rank: 2,295 | 84.26%
DOI: 10.14778/2732286.2732290

Incoming Non-self Citations Over Time

Authors

1. Semih Salihoglu (Stanford University)
2. Jennifer Widom (Stanford University)

BibTeX Citation

@article{salihoglu_vldb14,
        title = {{Optimizing Graph Algorithms on Pregel-like Systems}},
        author = {Salihoglu, Semih and Widom, Jennifer},
        journal = {PVLDB},
        series = {{VLDB} '14},
        volume = {7},
        number = {7},
        pages = {577--588},
        doi = {10.14778/2732286.2732290},
        url = {https://doi.org/10.14778/2732286.2732290},
        year = {2014}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,300	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00011258552
1,875	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	9.5728308e-05
2,325	Giraph Unchained: Barrierless Asynchronous Parallel Execution in Pregel-like Graph Processing Systems	2015	VLDB	8.7495171e-05
3,065	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.7989716e-05
3,752	Distributed Edge Partitioning for Trillion-edge Graphs	2019	VLDB	7.15217e-05
3,836	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	7.0827068e-05
9,605	Nezha: An Efficient Distributed Graph Processing System on Heterogeneous Hardware	2025	SIGMOD	5.247855e-05
9,748	Graft: A Debugging Tool For Apache Giraph	2015	SIGMOD	5.227679e-05
10,797	Using Process Calculus for Optimizing Data and Computation Sharing in Complex Stateful Parallel Computations	2025	SIGMOD	5.093636e-05
11,394	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	5.093636e-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
3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0012250108
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,207	Communication Steps for Parallel Query Processing	2013	PODS	0.00011663155
1,514	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010527649

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,450	Big Graph Analytics Systems	2016	SIGMOD
2	1,911	Fast Iterative Graph Computation with Block Updates	2013	VLDB
3	3,616	Parallel Local Graph Clustering	2016	VLDB
4	4,297	Graph Analytics Through Fine-Grained Parallelism	2016	SIGMOD
5	7,281	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB
6	1,300	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB
7	487	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB
8	1,875	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB
9	3,065	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB
10	3	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD