Projects per year
Abstract
We present a constantround 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^{Õ(m/p1/ρ}) where m is the total size of the input relations, p is the number of machines, ρ is the join’s fractional edge covering number, and Õ(.) 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 constantsized subgraph pattern, can be settled optimally (up to a polylogarithmic factor) in the MPC model.
Original language  English 

Pages (fromto)  6:16:22 
Number of pages  22 
Journal  Logical Methods in Computer Science 
Volume  18 
Issue number  2 
DOIs  
Publication status  Published  1 Jan 2022 
Keywords
 Conjunctive Queries
 Database Theory
 Joins
 Parallel Computing
Fingerprint
Dive into the research topics of 'A NEAROPTIMAL PARALLEL ALGORITHM FOR JOINING BINARY RELATIONS'. Together they form a unique fingerprint.Projects
 1 Active

FWOAL1008: Optimal Join Algorithms for Modern Distributed Data Systems
1/01/21 → 31/12/24
Project: Fundamental