论文标题
平行无环与规范的边缘盖
Parallel Acyclic Joins with Canonical Edge Covers
论文作者
论文摘要
在PODS'21中，HU在大规模并行计算（MPC）模型中提出了一种算法，该算法与任何无环与渐近的最佳负载一起加入。在本文中，我们对她的算法进行了替代分析。我们分析的新颖性是针对无环超图的新数学结构的启示（我们将其命名为“规范边缘盖”）。我们证明了规范边缘覆盖物的非平凡属性，这些特性为我们提供了关于HU算法为什么有效的图理论观点。
In PODS'21, Hu presented an algorithm in the massively parallel computation (MPC) model that processes any acyclic join with an asymptotically optimal load. In this paper, we present an alternative analysis of her algorithm. The novelty of our analysis is in the revelation of a new mathematical structure -- which we name "canonical edge cover" -- for acyclic hypergraphs. We prove non-trivial properties for canonical edge covers that offer us a graph-theoretic perspective about why Hu's algorithm works.
