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: 10880
Venue: VLDB
Year: 2014
Pagerank: 7.8823626e-05
Overall Rank: 2,927 | 79.64%
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
444	Parallelizing Sequential Graph Computations	2017	SIGMOD	0.00022987918
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
4,970	On Querying Connected Components in Large Temporal Graphs	2023	SIGMOD	5.7945079e-05
5,570	iTurboGraph: Scaling and Automating Incremental Graph Analytics	2021	SIGMOD	5.4284968e-05
7,402	A General-Purpose Query-Centric Framework for Querying Big Graphs	2016	VLDB	4.7392415e-05
7,607	Systems for Scalable Graph Analytics and Machine Learning: Trends and Methods	2025	VLDB	4.6967024e-05
7,871	ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms	2021	VLDB	4.6308128e-05
8,146	MiniGraph: Querying Big Graphs with a Single Machine	2023	VLDB	4.5755031e-05
9,477	Revisiting Graph Analytics Benchmark	2025	SIGMOD	4.3341665e-05
10,873	A Single Machine System for Querying Big Graphs with PRAM	2025	VLDB	4.1945683e-05
11,191	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1945683e-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.0019005923
37	Distributed GraphLab: A Framework for Machine Learning and Data Mining in the Cloud	2012	VLDB	0.0007522744
686	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00018178029
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
1,880	TF-Label: a Topological-Folding Labeling Scheme for Reachability Querying in a Large Graph	2013	SIGMOD	0.00010226347
2,336	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0109891e-05
2,674	Minimal MapReduce Algorithms	2013	SIGMOD	8.3328645e-05
4,067	Efficient Processing of Distance Queries in Large Graphs: A Vertex Cover Approach	2012	SIGMOD	6.4795399e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
574	From "Think Like a Vertex" to "Think Like a Graph"	2014	VLDB	0.00019883211
1,408	An Experimental Comparison of Pregel-like Graph Processing Systems	2014	VLDB	0.00012133511
2,542	Scalable Discovery of Best Clusters on Large Graphs	2010	VLDB	8.5794502e-05
1,171	Blogel: A Block-Centric Framework for Distributed Computation on Real-World Graphs	2014	VLDB	0.00013511313
11,191	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1945683e-05
6,207	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	5.1572428e-05
3,129	Scalable Big Graph Processing in MapReduce	2014	SIGMOD	7.5008242e-05
1,877	Large-Scale Distributed Graph Computing Systems: An Experimental Evaluation	2015	VLDB	0.00010236803
4	Pregel: A System for Large-Scale Graph Processing	2010	SIGMOD	0.0019005923
2,336	Optimizing Graph Algorithms on Pregel-like Systems	2014	VLDB	9.0109891e-05