文章基本信息

标题：A Simple Parallel Algorithm for Natural Joins on Binary Relations
本地全文：下载
作者：Yufei Tao
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：155
页码：25:1-25:18
DOI：10.4230/LIPIcs.ICDT.2020.25
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：In PODS'17, Ketsman and Suciu gave an algorithm in the MPC model for computing the result of any natural join where every input relation has two attributes. Achieving an optimal load O(m/p^{1/Ï}) - where m is the total size of the input relations, p the number of machines, and Ï the fractional edge covering number of the join - their algorithm requires 7 rounds to finish. This paper presents a simpler algorithm that ensures the same load with 3 rounds (in fact, the second round incurs only a load of O(pÂ²) to transmit certain statistics to assist machine allocation in the last round). Our algorithm is made possible by a new theorem that provides fresh insight on the structure of the problem, and brings us closer to understanding the intrinsic reason why joins on binary relations can be settled with load O(m/p^{1/Ï}).
关键词：Natural Joins; Conjunctive Queries; MPC Algorithms; Parallel Computing