RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs

Summary: RECEIPT parallelizes bipartite tip decomposition by relaxing minimum-butterfly peeling into coarsely grained independent vertex tasks, reducing synchronization and wedge exploration. A hybrid peeling strategy yields up to 1100× fewer synchronizations, 64× fewer wedges, and 17.1× speedup. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h890579140c0b5580
Venue: VLDB
Year: 2021
Pagerank: 5.4575542e-05
Overall Rank: 7,753 | 47.90%
DOI: 10.14778/3430915.3430929
PDF: Download (CC BY-NC-ND 4.0)

Incoming Non-self Citations Over Time

Authors

1. Kartik Lakhotia (University of Southern California)
2. Rajgopal Kannan (U.S. Army Research Laboratory)
3. Viktor Prasanna (University of Southern California)
4. Cesar A. F. De Rose (Pontifical Catholic University of Rio Grande do Sul)

BibTeX Citation

@article{lakhotia_vldb21,
        title = {{RECEIPT: REfine CoarsE-grained IndePendent Tasks for Parallel Tip decomposition of Bipartite Graphs}},
        author = {Lakhotia, Kartik and Kannan, Rajgopal and Prasanna, Viktor and De Rose, Cesar A. F.},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {3},
        pages = {404--417},
        doi = {10.14778/3430915.3430929},
        url = {https://doi.org/10.14778/3430915.3430929},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB	5.9272031e-05
9,878	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.115241e-05
11,337	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	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
264	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022768034
563	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016319495
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,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012007739
1,224	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011458287
1,438	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010647473
1,444	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010630508
1,648	Distance-generalized Core Decomposition	2019	SIGMOD	9.9816501e-05
1,664	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.9394611e-05
1,853	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.499042e-05
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,190	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8832666e-05
5,604	Ego-net Community Mining Applied to Friend Suggestion	2016	VLDB	6.0671173e-05
9,175	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2123828e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,631	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD
2	5,721	Local Algorithms for Distance-generalized Core Decomposition over Large Dynamic Graphs	2021	VLDB
3	5,976	Theoretically and Practically Efficient Parallel Nucleus Decomposition	2022	VLDB
4	9,403	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB
5	5,141	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB
6	1,224	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB
7	9,872	Density Decomposition of Bipartite Graphs	2025	SIGMOD
8	8,077	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
9	6,655	Efficient Parallel D-core Decomposition at Scale	2024	VLDB
10	7,284	Towards Distributed Bitruss Decomposition on Bipartite Graphs	2022	VLDB