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: 14152
Venue: VLDB
Year: 2025
Pagerank: 5.093636e-05
Overall Rank: 10,919 | 25.09%
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 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

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
264	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00022980015
1,036	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00012499878
2,199	Real-time Targeted Influence Maximization for Online Advertisements	2015	VLDB	8.9668012e-05
2,288	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	8.8025299e-05
2,940	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	7.9381573e-05
4,667	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	6.5768564e-05
4,916	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	6.4474058e-05
6,023	On Optimal Worst-Case Matching	2013	SIGMOD	6.0032138e-05
6,345	Clustering Uncertain Graphs	2018	VLDB	5.9059861e-05
6,924	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	5.738697e-05
7,067	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	5.7120928e-05
7,492	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD	5.6047664e-05
7,578	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	5.5927377e-05
8,019	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	5.5062157e-05
8,227	From Anomaly Detection to Rumour Detection using Data Streams of Social Platforms	2019	VLDB	5.4622609e-05
9,432	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	5.2701501e-05
9,814	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	5.214913e-05
9,815	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	5.214913e-05
9,822	Mining Revenue-Maximizing Bundling Configuration	2015	VLDB	5.214913e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,006	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD
2	10,564	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB
3	442	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB
4	10,204	Beyond Maximum Common Subgraph: A Framework Maximizing Shared Computation for Multi-Query Subgraph Matching	2026	SIGMOD
5	3,821	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB
6	11,756	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD
7	2,650	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD
8	1,128	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB
9	10,375	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD
10	10,558	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB