X-Blossom: Massive Parallelization of Graph Maximum Matching

Summary: X-Blossom: recursion-free parallelization of Edmonds' blossom that finds many disjoint augmenting paths via a compact path table, removing dynamic graph/tree updates. Delivers up to 992× vs best sequential and avg 431× vs prior parallel (8 cores), with good scaling to 64 cores—claimed fastest general-graph max-matching. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 13965
Venue: VLDB
Year: 2025
Pagerank: 4.1905499e-05
Overall Rank: 10,678 | 25.79%
DOI: 10.14778/3748191.3748199

Incoming Non-self Citations Over Time

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

Authors

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
327	The Ubiquity of Large Graphs and Surprising Challenges of Graph Processing	2018	VLDB	0.00027312381
1,487	Parallel Subgraph Listing in a Large-Scale Graph	2014	SIGMOD	0.00011691164
1,857	Real-time Targeted Influence Maximization for Online Advertisements	2015	VLDB	0.00010318371
2,933	Pangolin: An Efficient and Flexible Graph Mining System on CPU and GPU	2020	VLDB	7.8633648e-05
3,644	G-CARE: A Framework for Performance Benchmarking of Cardinality Estimation Techniques for Subgraph Matching	2020	SIGMOD	6.8842065e-05
4,927	Efficient Cohesive Subgraphs Detection in Parallel	2014	SIGMOD	5.8181623e-05
5,599	Neighborhood-based Hypergraph Core Decomposition	2023	VLDB	5.4164926e-05
5,979	On Optimal Worst-Case Matching	2013	SIGMOD	5.242029e-05
6,522	Clustering Uncertain Graphs	2018	VLDB	5.0230003e-05
7,304	SUFF: Accelerating Subgraph Matching with Historical Data	2023	VLDB	4.7628386e-05
7,714	Minimum Strongly Connected Subgraph Collection in Dynamic Graphs	2024	VLDB	4.6651585e-05
7,745	Scalable Distributed Inverted List Indexes in Disaggregated Memory	2024	SIGMOD	4.6578829e-05
8,375	From Anomaly Detection to Rumour Detection using Data Streams of Social Platforms	2019	VLDB	4.5278191e-05
8,809	Efficient Maximal Motif-Clique Enumeration over Large Heterogeneous Information Networks	2024	VLDB	4.4401156e-05
9,272	PimPam: Efficient Graph Pattern Matching on Real Processing-in-Memory Hardware	2024	SIGMOD	4.3621803e-05
9,367	MITra: A Framework for Multi-Instance Graph Traversal	2023	VLDB	4.3466395e-05
9,679	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	4.3006524e-05
9,680	PCSP: Efficiently Answering Label-Constrained Shortest Path Queries in Road Networks	2024	VLDB	4.3006524e-05
9,686	Mining Revenue-Maximizing Bundling Configuration	2015	VLDB	4.3006524e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
11,193	Parallel Strong Connectivity Based on Faster Reachability	2023	SIGMOD	4.1905499e-05
1,522	Efficient Subgraph Matching: Harmonizing Dynamic Programming, Adaptive Matching Order, and Failing Set Together	2019	SIGMOD	0.0001152219
10,276	gMatch: Fine-Grained and Hardware-Efficient Subgraph Matching on GPUs	2026	VLDB	4.1905499e-05
648	Efficient Subgraph Matching on Billion Node Graphs	2012	VLDB	0.00018688754
4,554	Distributed Subgraph Matching on Timely Dataflow	2019	VLDB	6.0839934e-05
11,563	Approximate Pattern Matching in Massive Graphs with Precision and Recall Guarantees	2020	SIGMOD	4.1905499e-05
2,402	TreeSpan: Efficiently Computing Similarity All-Matching	2012	SIGMOD	8.87387e-05
1,419	Graph Pattern Matching: From Intractable to Polynomial Time	2010	VLDB	0.00012072488
10,084	GraphMatch: Subgraph Query Processing on Steroids	2026	SIGMOD	4.1905499e-05
10,270	Characterizing Parallel Subgraph Matching Performance: A Systematic Study of Interactions, Scalability, and Enumeration	2026	VLDB	4.1905499e-05