Theoretically and Practically Efficient Parallel Nucleus Decomposition

Summary: Parallel nucleus decomposition with work matching the best sequential bounds and low depth, surpassing PVLDB 2018's parallel method. Key ideas: clique-peeling bound, parallel clique listing/bucketing, and cache-friendly multi-level hash tables, delivering up to 55x speedup on 30 cores. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12932
Venue: VLDB
Year: 2022
Pagerank: 4.8970985e-05
Overall Rank: 6,880 | 52.14%
DOI: 10.14778/3494124.3494140

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,513	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0321577e-05
10,495	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1945683e-05
10,947	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1945683e-05
11,048	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 18 of 18 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
57	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00065491112
108	Truss Decomposition in Massive Networks	2012	VLDB	0.00048300163
283	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00029041257
738	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00017435236
1,029	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00014582849
1,150	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013657353
1,530	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00011495611
1,550	Approximate Closest Community Search in Networks	2016	VLDB	0.00011423628
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
2,846	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.0234377e-05
2,909	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	7.9305767e-05
3,321	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.223972e-05
3,597	Parallel Local Graph Clustering	2016	VLDB	6.9345175e-05
3,975	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	6.5736847e-05
5,417	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	5.5194222e-05
7,804	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	4.6466513e-05
9,862	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	4.2683554e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
966	Streaming Algorithms for k-core Decomposition	2013	VLDB	0.00014960672
9,146	Accelerating Core Decomposition in Billion-Scale Hypergraphs	2025	SIGMOD	4.3849295e-05
1,836	Distance-generalized Core Decomposition	2019	SIGMOD	0.00010365753
2,512	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	8.6196023e-05
9,951	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB	4.2405999e-05
2,039	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	9.7061003e-05
6,141	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB	5.1903263e-05
6,513	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.0321577e-05
10,495	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	4.1945683e-05
10,947	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	4.1945683e-05