Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees

Summary: Proposes Practical Pregel Algorithms (PPAs) with linear space, per-iteration cost bounds, and logarithmic iterations for distributed graph connectivity. PPAs for CCs, BCCs, SCCs built from building-block PPAs; experiments on large real graphs confirm efficiency. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 10881
Venue: VLDB
Year: 2014
Pagerank: 7.9062736e-05
Overall Rank: 2,916 | 79.74%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
441	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00023172424
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
4,726	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.9632682e-05
5,573	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4268881e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7346959e-05
7,609	Systems for Scalable Graph Analytics and Machine Learning: Trends and Methods	2025	VLDB	4.6921981e-05
7,874	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6263724e-05
8,152	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5711161e-05
9,479	Revisiting Graph Analytics Benchmark	2025	SIGMOD	4.3300131e-05
10,877	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB	4.1905499e-05
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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
39	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.00075263552
682	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.0001816451
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
1,879	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010227906
2,332	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0173968e-05
2,714	Minimal MapReduce Algorithms	2013	SIGMOD	8.2426646e-05
4,070	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4739921e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
570	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019895021
1,410	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012127229
2,541	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5710863e-05
1,170	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013526297
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-05
6,206	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1522897e-05
3,188	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.4142307e-05
1,876	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010242818
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019040811
2,332	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0173968e-05