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]

• Developed the first large-scale parallel framework for maximum/minimum weight perfect matching in bipartite graphs
• Proposed phase-decoupled sequential and parallel Hungarian algorithms with optimized multicore implementations
• Enables efficient large-scale assignment and matching for cloud resource allocation, multi-robot coordination, and marketplace platforms

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]

• Developed the first large-scale parallel framework for maximum matching
• Proposed recursion-free sequential and parallel Blossom algorithms that eliminate dynamic graph contraction, implemented on multicore CPUs
• Supports high-performance graph applications in financial analysis, social platforms, and recommendation systems

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]

• Developed the first large-scale parallel framework for tree edit distance
• Proposed a novel algorithm that breaks complex dynamic programming dependencies, with optimized multicore CPU and GPU implementations
• Facilitates efficient tree-structured data comparison in LLM evaluation workflows, code analysis, and hierarchical data processing