一句话：提出 MPC 模型下连接二元关系的常数轮近优并行算法，负载达到已知下界（至多 polylog 因子）。
本文研究大规模并行计算（MPC）模型中，如何高效计算每条输入关系仅含两个属性的自然连接。作者提出一个常数轮算法，其负载为 Õ(m/p^{1/ρ})，其中 m 为输入关系总大小，p 为机器数，ρ 为连接的分数边覆盖数，该负载与已知下界仅差 polylog 因子。算法核心是一个新的“孤立笛卡尔积定理”，揭示了问题的数学结构。该结果还表明，子图枚举问题（报告所有常数大小子图模式的出现）在 MPC 模型中可近似最优解决。
We present a constant-round algorithm in the massively parallel computation (MPC) model for evaluating a natural join where every input relation has two attributes. Our algorithm achieves a load of $\tilde{O}(m/p^{1/\rho})$ where $m$ is the total size of the input relations, $p$ is the number of machines, $\rho$ is the join's fractional edge covering number, and $\tilde{O}(.)$ hides a polylogarithmic factor. The load matches a known lower bound up to a polylogarithmic factor. At the core of the proposed algorithm is a new theorem (which we name the "isolated cartesian product theorem") that provides fresh insight into the problem's mathematical structure. Our result implies that the subgraph enumeration problem, where the goal is to report all the occurrences of a constant-sized subgraph pattern, can be settled optimally (up to a polylogarithmic factor) in the MPC model.
@article{paperbot1705,
title = {A Near-Optimal Parallel Algorithm for Joining Binary Relations},
author = {Bas Ketsman and Dan Suciu and Yufei Tao},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 2},
year = {2022},
doi = {10.46298/lmcs-18(2:6)2022}
}