I/O Efficient ECC Graph Decomposition via Graph Reduction

Summary: I/O efficient ECC decomposition for all k values achieved via two graph-reduction operators that shrink the in-memory graph while preserving k-edge connectivity. Bottom-Up, Top-Down, and Hybrid algorithms explore k-values in different orders to minimize redundant work, with experiments on graphs up to 1.95B edges demonstrating scalability. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h57d320c6716f431f
Venue: VLDB
Year: 2016
Pagerank: 5.8487355e-05
Overall Rank: 6,211 | 58.25%
DOI: 10.14778/2904483.2904484

Incoming Non-self Citations Over Time

Authors

1. Long Yuan (University of New South Wales)
2. Lu Qin (University of Technology Sydney)
3. Xuemin Lin (University of New South Wales)
4. Lijun Chang (University of New South Wales)
5. Wenjie Zhang (University of New South Wales)

BibTeX Citation

@article{yuan_vldb16,
        title = {{I/O Efficient ECC Graph Decomposition via Graph Reduction}},
        author = {Yuan, Long and Qin, Lu and Lin, Xuemin and Chang, Lijun and Zhang, Wenjie},
        journal = {PVLDB},
        series = {{VLDB} '16},
        volume = {9},
        number = {7},
        doi = {10.14778/2904483.2904484},
        url = {https://doi.org/10.14778/2904483.2904484},
        year = {2016}
}

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,141	Efficient Shortest Path Index Maintenance on Dynamic Road Networks with Theoretical Guarantees	2020	VLDB	8.9668034e-05
2,869	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9235321e-05
3,875	Cohesive Subgraph Search over Big Heterogeneous Information Networks: Applications, Challenges, and Solutions	2021	SIGMOD	6.9536357e-05
8,772	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB	5.2806308e-05
9,677	Efficient Maximum s-Bundle Search via Local Vertex Connectivity	2025	SIGMOD	5.1435978e-05
9,805	I/O Efficient Label-Constrained Reachability Queries in Large Graphs	2024	VLDB	5.1257999e-05
9,868	A Flexible Framework for Query-oriented Interactive Community Search	2025	VLDB	5.1176637e-05
10,442	Efficient Anchored Densest Subgraph Discovery: Improved Time Complexity and Practical Performance	2026	SIGMOD	4.9793485e-05
10,808	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9793485e-05
11,220	In-depth Analysis of Densest Subgraph Discovery in a Unified Framework	2025	VLDB	4.9793485e-05
11,321	Efficient k-Clique Densest Subgraph Discovery: Towards Bridging Practice and Theory	2025	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 10 of 10 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
100	Truss Decomposition in Massive Networks	2012	VLDB	0.00033977856
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015905948
600	Massive Graph Triangulation	2013	SIGMOD	0.00015740352
645	Finding Maximal Cliques in Massive Networks by H*-graph	2010	SIGMOD	0.00015213733
3,168	GConnect: A Connectivity Index for Massive Disk-Resident Graphs	2009	VLDB	7.5723309e-05
3,328	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD	7.4193937e-05
5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD	6.0472942e-05
9,936	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD	5.1074935e-05
12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD	4.9793485e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB
2	10,636	Efficient Influential Community Search over Dynamic Graphs	2026	SIGMOD
3	3,328	Index-based Optimal Algorithms for Computing Steiner Components with Maximum Connectivity	2015	SIGMOD
4	9,915	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB
5	9,936	Divide & Conquer: I/O Efficient Depth-First Search	2015	SIGMOD
6	3,860	Efficient Maximum k-Defective Clique Computation with Improved Time Complexity	2023	SIGMOD
7	758	Streaming Algorithms for k-core Decomposition	2013	VLDB
8	12,530	I/O Efficient: Computing SCCs in Massive Graphs	2013	SIGMOD
9	8,772	A Near-Optimal Approach to Edge Connectivity-Based Hierarchical Graph Decomposition	2022	VLDB
10	5,662	Efficiently Computing k-Edge Connected Components via Graph Decomposition	2013	SIGMOD