X-Wim: Massive Parallelization of Weighted Matching in Bipartite Graphs

Dayi Fan, Simon Zhang, Rubao Lee, Hanqi Guo, Xiaodong Zhang

The 52^nd International Conference on Very Large Data Bases (VLDB 2026)

[PDF] [Code] [Slides]

• The first scalable parallel framework for bipartite weighted matching, a fundamental problem in user paring, object tracking, and entity resolution
• Introduces a new phase-decoupled Hungarian algorithm that breaks the tight interleaving between path search and label updates, enabling massive search concurrency while substantially reducing synchronization
• Outperforms state-of-the-art baselines by up to 10x on one core and scales to 96 cores with an average 1.7x speedup per thread doubling

X-Blossom: Massive Parallelization of Graph Maximum Matching

Dayi Fan, Rubao Lee, Xiaodong Zhang

The 51^st International Conference on Very Large Data Bases (VLDB 2025)

[PDF] [Code] [Slides]

• The first scalable parallel framework for maximum matching, a critical primitive in graph databases, network scheduling, and service dispatch
• Proposes a new recursion-free Blossom algorithm that eliminates dynamic graph contraction, thereby removing strong recursive dependencies and exposing massive parallelism
• Surpasses prior state-of-the-art matching solutions significantly, achieving speedups of up to three orders of magnitude

X-TED: Massive Parallelization of Tree Edit Distance

Dayi Fan, Rubao Lee, Xiaodong Zhang

The 50^th International Conference on Very Large Data Bases (VLDB 2024)

[PDF] [Code] [Slides]

• The first scalable parallel framework for tree edit distance, with broad applications including code analysis and LLM output evaluation
• Develops a new algorithm that infers intricate data dependencies among dynamic-programming tables from input tree structures with negligible overhead and batches independent tables for concurrent processing
• Achieves speedups of up to 31x over prior parallel solutions