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: 12771
Venue: VLDB
Year: 2021
Pagerank: 5.5302333e-05
Overall Rank: 7,862 | 46.07%
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,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.7459836e-05
11,102	The ParClusterers Benchmark Suite (PCBS): A Fine-Grained Analysis of Scalable Graph Clustering	2025	VLDB	5.093636e-05
11,105	Towards Scalable and Practical Batch-Dynamic Connectivity	2025	VLDB	5.093636e-05
11,286	Fast and Space-Efficient Parallel Algorithms for Influence Maximization	2024	VLDB	5.093636e-05
11,394	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	5.093636e-05
11,581	ParChain: A Framework for Parallel Hierarchical Agglomerative Clustering using Nearest-Neighbor Chain	2022	VLDB	5.093636e-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
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
706	Effective Community Search for Large Attributed Graphs	2016	VLDB	0.00014789612
962	DBSCAN Revisited: Mis-Claim, Un-Fixability, and Approximation	2015	SIGMOD	0.00012936472
2,482	Efficient Structural Graph Clustering: An Index-Based Approach	2018	VLDB	8.5183361e-05
3,065	Pregel Algorithms for Graph Connectivity Problems with Performance Guarantees	2014	VLDB	7.7989716e-05
3,175	Single Machine Graph Analytics on Massive Datasets Using Intel Optane DC Persistent Memory	2020	VLDB	7.6656917e-05
4,358	Parallel Index-Based Structural Graph Clustering and Its Approximation	2021	SIGMOD	6.7459836e-05
10,011	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.1772034e-05
11,825	Parallel Graph Algorithms in Constant Adaptive Rounds: Theory meets Practice	2020	VLDB	5.093636e-05

Semantically Similar Papers

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