Theoretically and Practically Efficient Parallel Nucleus Decomposition

Summary: A work-optimal, low-depth parallel nucleus decomposition via a new clique-peeling bound, scalable clique listing/bucketing, and cache-efficient multi-level hashing. Practical optimizations deliver up to 55× speedup and enable million-scale decompositions. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h2e2b6e1e0dd5a1b5
Venue: VLDB
Year: 2022
Pagerank: 5.9272031e-05
Overall Rank: 5,976 | 59.84%
DOI: 10.14778/3494124.3494140
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Jessica Shi (Massachusetts Institute of Technology)
2. Laxman Dhulipala (Massachusetts Institute of Technology)
3. Julian Shun (Massachusetts Institute of Technology)

BibTeX Citation

@article{shi_vldb22,
        title = {{Theoretically and Practically Efficient Parallel Nucleus Decomposition}},
        author = {Shi, Jessica and Dhulipala, Laxman and Shun, Julian},
        journal = {PVLDB},
        series = {{VLDB} '22},
        volume = {15},
        number = {3},
        pages = {583--596},
        doi = {10.14778/3494124.3494140},
        url = {https://doi.org/10.14778/3494124.3494140},
        year = {2022}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,655	Efficient Parallel D-core Decomposition at Scale	2024	VLDB	5.717615e-05
8,077	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD	5.3917406e-05
9,878	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.115241e-05
9,922	Efficient Algorithms for Density Decomposition on Large Static and Dynamic Graphs	2024	VLDB	5.1079647e-05
10,496	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD	4.9769913e-05
10,818	Efficient Locally h-Clique Densest Subgraph Discovery via Divide-and-Conquer	2026	VLDB	4.9769913e-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
100	Truss Decomposition in Massive Networks	2012	VLDB	0.0003396253
131	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00030236369
184	Querying K-Truss Community in Large and Dynamic Graphs	2014	SIGMOD	0.00026097449
589	Large Scale Cohesive Subgraphs Discovery for Social Network Visual Analysis	2013	VLDB	0.00015898419
834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013576778
988	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012654453
1,092	Truss-based Community Search: a Truss-equivalence Based Indexing Approach	2017	VLDB	0.00012066667
1,130	Approximate Closest Community Search in Networks	2016	VLDB	0.00011897973
1,444	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010630508
2,044	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.1373547e-05
2,121	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.0060232e-05
2,288	Unboundedness and Efficiency of Truss Maintenance in Evolving Graphs	2019	SIGMOD	8.6907426e-05
2,869	Hierarchical Core Maintenance on Large Dynamic Graphs	2021	VLDB	7.9197812e-05
3,495	Accelerating Truss Decomposition on Heterogeneous Processors	2020	VLDB	7.2527929e-05
3,690	Parallel Local Graph Clustering	2016	VLDB	7.0919971e-05
5,421	Theoretically-Efficient and Practical Parallel DBSCAN	2020	SIGMOD	6.1355031e-05
7,753	RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs	2021	VLDB	5.4575542e-05
10,208	Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs	2020	VLDB	5.0586451e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,648	Distance-generalized Core Decomposition	2019	SIGMOD
2	10,334	Parallel Colorful h-star Core Maintenance in Dynamic Graphs	2023	VLDB
3	2,121	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB
4	1,444	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB
5	10,884	Resource-Efficient FirmCore Decomposition on Billion-scale Multilayer Graphs	2026	VLDB
6	5,721	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
7	6,655	Efficient Parallel D-core Decomposition at Scale	2024	VLDB
8	8,077	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
9	10,496	Nucleus Decomposition Revisited: An Efficient Counting-Based Approach	2026	SIGMOD
10	9,878	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD