ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms

Summary: ConnectIt systematically combines sampling, tree-linking, and compression into hundreds of static and concurrent incremental connectivity variants. On 72 cores, it delivers 12.4× average speedups, processes a 3.5B-vertex graph in under 10 seconds, and ingests billions of edges/s. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hce04ce8f579bdfd8
Venue: VLDB
Year: 2021
Pagerank: 5.4105956e-05
Overall Rank: 7,997 | 46.24%
DOI: 10.14778/3436905.3436923

Incoming Non-self Citations Over Time

Authors

1. Laxman Dhulipala (Massachusetts Institute of Technology)
2. Changwan Hong (Massachusetts Institute of Technology)
3. Julian Shun (Massachusetts Institute of Technology)

BibTeX Citation

@article{dhulipala_vldb21,
        title = {{ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms}},
        author = {Dhulipala, Laxman and Hong, Changwan and Shun, Julian},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {4},
        pages = {653--667},
        doi = {10.14778/3436905.3436923},
        url = {https://doi.org/10.14778/3436905.3436923},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,451	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.5946218e-05
9,963	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.1038322e-05
11,452	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	4.9793485e-05
11,455	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	4.9793485e-05
11,709	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.9793485e-05
11,889	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
714	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014569079
986	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012668888
2,540	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.3274854e-05
3,107	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.6420848e-05
3,244	Single Machine Graph Analytics on Massive Datasets Using Intel Optane DC Persistent Memory	2020	VLDB	7.4970778e-05
4,451	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.5946218e-05
10,202	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.0610409e-05
12,126	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,688	Parallel Local Graph Clustering	2016	VLDB
2	3,328	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
3	3,107	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB
4	7,015	A Hierarchical Contraction Scheme for Querying Big Graphs	2022	SIGMOD
5	1,963	Fast Iterative Graph Computation with Block Updates	2013	VLDB
6	5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD
7	11,709	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD
8	3,168	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB
9	11,540	Constant-time Connectivity Querying in Dynamic Graphs	2024	SIGMOD
10	11,455	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB