The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication

Abstract

Given a set-comparison predicate P and given two lists of sets A = (A1, ... ,Am) and B = (B1, ... ,Bm), with all Ai,Bj ⊆ [n], the P-set join A ▹P B is defined to be the set f(i, j) ε [m] × [m] j P(Ai,Bj)g ([n] denotes {1,2, ... , n}). When P(Ai,Bj) is the condition "Ai ∪ Bj= φ" we call this the set-intersection-notempty join (a.k.a. the composition of A and B); when P(Ai,Bj) is "Ai∩Bj = φ" we call it the set-disjointness join; when P(Ai,Bj) is "Ai = Bj" we call it the set-equality join; when P(Ai,Bj) is "|Ai ∩ Bj| ≥ T" for a given threshold T, we call it the setintersection threshold join. Assuming A and B are stored at two different sites in a distributed environment, we study the (randomized) communication complexity of computing these, and related, set-joins A ▹P B, as well as the (randomized) communication complexity of computing the exact and approximate value of their size k = jA ▹P Bj. Combined, our analyses shed new insights into the quantitative differences between these different set-joins. Furthermore, given the close affinity of the natural join and the setintersection- not-empty join, our results also yield communication complexity results for computing the natural join in a distributed environment. Additionally, we obtain new algorithms for computing the distributed set-intersection-not-empty join when the input and/or output is sparse. For instance, when the output is k-sparse, we improve an Ö(kn) communication algorithm of (Williams and Yu, SODA 2014). Observing that the set-intersection-not-empty join is isomorphic to Boolean matrix multiplication (BMM), our results imply new algorithms for fundamental graph theoretic problems related to BMM. For example, we show how to compute the transitive closure of a directed graph in Ö(k3/2) time, when the transitive closure contains at most k edges. When k = O(n), we obtain a (practical) Ö (n3=2) time algorithm, improving a recent Ö(n · n ω+1 4 ) time algorithm (Borassi, Crescenzi, and Habib, arXiv 2014) based on (impractical) fast matrix multiplication, where ω ≥ 2 is the exponent for matrix multiplication.