A Near-Optimal Parallel Algorithm for Joining Binary Relations

Bas Ketsman, Dan Suciu, Yufei Tao

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 a…