10.46298/lmcs-18(2:6)2022
https://lmcs.episciences.org/6944
Ketsman, Bas
Bas
Ketsman
0000-0002-4032-0709
Suciu, Dan
Dan
Suciu
Tao, Yufei
Yufei
Tao
0000-0003-3883-5452
A Near-Optimal Parallel Algorithm for Joining Binary Relations
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.
episciences.org
Computer Science - Databases
Attribution 4.0 International (CC BY 4.0)
2022-02-03
2022-05-05
2022-05-05
eng
journal article
arXiv:2011.14482
10.48550/arXiv.2011.14482
1860-5974
https://lmcs.episciences.org/6944/pdf
VoR
application/pdf
Logical Methods in Computer Science
Volume 18, Issue 2
Researchers
Students