文章基本信息

标题：A NEAR-OPTIMAL PARALLEL ALGORITHM FOR JOINING BINARY RELATIONS
本地全文：下载
作者：Bas Ketsman ; Dan Suciu ; Yufei Tao 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2022
卷号：18
期号：2
页码：1-22
DOI：10.46298/lmcs-18(2:6)2022
语种：English
出版社：Technical University of Braunschweig
摘要：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.
关键词：Joins;Conjunctive Queries;Parallel Computing;Database Theory