X-Blossom: Massive Parallelization of Graph Maximum Matching

Summary: X-Blossom massively parallelizes maximum matching by eliminating recursion, concurrently searching disjoint augmenting paths, and replacing dynamic graph/tree structures with a simple path table. Achieves up to 992× sequential and 431× prior-parallel speedups, with scalability to 64 cores. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: h7cf2c238860fede4
Venue: VLDB
Year: 2025
Pagerank: 4.9793485e-05
Overall Rank: 11,312 | 23.95%
DOI: 10.14778/3748191.3748199

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Dayi Fan (Ohio State University)
2. Rubao Lee (Independent)
3. Xiaodong Zhang (Ohio State University)

BibTeX Citation

@article{fan_vldb25,
        title = {{X-Blossom: Massive Parallelization of Graph Maximum Matching}},
        author = {Fan, Dayi and Lee, Rubao and Zhang, Xiaodong},
        journal = {PVLDB},
        series = {{VLDB} '25},
        volume = {18},
        number = {10},
        pages = {3339--3353},
        doi = {10.14778/3748191.3748199},
        url = {https://doi.org/10.14778/3748191.3748199},
        year = {2025}
}

Incoming Citations (Sorted by Pagerank)

Showing 1 of 1 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,813	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 19 of 19 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
239	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.000235107
1,046	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012319866
2,229	Real-time Targeted Influence Maximization for Online Advertisements	2015	VLDB	8.8000047e-05
2,469	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	8.4165523e-05
2,824	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9698957e-05
4,314	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.6695257e-05
4,755	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.4323525e-05
6,155	On Optimal Worst-Case Matching	2013	SIGMOD	5.8685178e-05
6,475	Clustering Uncertain Graphs	2018	VLDB	5.7736095e-05
6,515	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	5.7590881e-05
6,893	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	5.6540469e-05
7,631	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD	5.4798152e-05
7,724	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.4672516e-05
8,178	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	5.382671e-05
8,399	From Anomaly Detection to Rumour Detection using Data Streams of Social Platforms	2019	VLDB	5.3397056e-05
9,613	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	5.1519021e-05
10,003	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.0979044e-05
10,004	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.0979044e-05
10,010	Mining Revenue-Maximizing Bundling Configuration	2015	VLDB	5.0979044e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,746	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
2	443	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
3	10,420	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD
4	3,880	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB
5	2,702	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD
6	12,059	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
7	1,148	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
8	10,270	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD
9	10,740	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB
10	10,813	X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs	2026	VLDB