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.4601389e-05
Overall Rank: 7,747 | 47.92%
DOI: 10.14778/3430915.3430929

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.9300103e-05
9,871	Parallel Algorithms for Hierarchical Nucleus Decomposition	2024	SIGMOD	5.1176637e-05
11,329	Effective and Efficient Community Search for Complex Network Semantics Capture: From Coarse-Grain to Fine-Grain	2025	VLDB	4.9793485e-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.00033977856
131	Discovering Large Dense Subgraphs in Massive Graphs	2005	VLDB	0.00030242586
265	On Triangulation-based Dense Neighborhood Graph Discovery	2011	VLDB	0.00022748633
563	Graph Summarization with Bounded Error	2008	SIGMOD	0.00016327158
834	K-Core Decomposition of Large Networks on a Single PC	2016	VLDB	0.00013583208
988	Dense Subgraph Maintenance under Streaming Edge Weight Updates for Real-time Story Identification	2012	VLDB	0.00012660447
1,100	CECI: Compact Embedding Cluster Index for Scalable Subgraph Matching	2019	SIGMOD	0.00012013426
1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB	0.00011463714
1,440	Speedup Graph Processing by Graph Ordering	2016	SIGMOD	0.00010641888
1,443	Local Algorithms for Hierarchical Dense Subgraph Discovery	2019	VLDB	0.00010635542
1,648	Distance-generalized Core Decomposition	2019	SIGMOD	9.9863775e-05
1,663	Effective and Efficient Community Search over Large Heterogeneous Information Networks	2020	VLDB	9.9441685e-05
2,019	Speeding Up Set Intersections in Graph Algorithms using SIMD Instructions	2018	SIGMOD	9.1750421e-05
2,042	Efficient Algorithms for Densest Subgraph Discovery	2019	VLDB	9.1416822e-05
2,119	Fast Hierarchy Construction for Dense Subgraphs	2017	VLDB	9.0102885e-05
2,188	Scaling Distance Labeling on Small-World Networks	2019	SIGMOD	8.8874739e-05
5,603	Ego-net Community Mining Applied to Friend Suggestion	2016	VLDB	6.0699908e-05
9,166	Planting Trees for scalable and efficient Canonical Hub Labeling	2020	VLDB	5.2148514e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,629	Efficient Core Maintenance in Large Bipartite Graphs	2023	SIGMOD
2	5,720	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,394	GraphTwist: Fast Iterative Graph Computation with Two-tier Optimizations	2015	VLDB
5	5,139	Efficient Load-Balanced Butterfly Counting on GPU	2022	VLDB
6	1,222	Vertex Priority Based Butterfly Counting for Large-scale Bipartite Networks	2019	VLDB
7	9,865	Density Decomposition of Bipartite Graphs	2025	SIGMOD
8	8,070	Parallel k-Core Decomposition: Theory and Practice	2025	SIGMOD
9	6,651	Efficient Parallel D-core Decomposition at Scale	2024	VLDB
10	7,281	Towards Distributed Bitruss Decomposition on Bipartite Graphs	2022	VLDB