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

Summary: Characterizes randomized communication complexity of distributed set-joins (intersection, disjointness, equality, threshold), yielding quantitative separations and consequences for distributed natural joins and join-size estimation. Provides sparse-output algorithms via BMM that improve O~(k n) and give transitive closure in O~(k^{3/2}) (O~(n^{3/2}) if k=O(n)). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h740b2886a7f45445
Venue: PODS
Year: 2015
Pagerank: 5.8773159e-05
Overall Rank: 6,122 | 58.86%
DOI: 10.1145/2745754.2745779

Incoming Non-self Citations Over Time

Authors

1. Dirk Van Gucht (Indiana University)
2. Ryan Williams (Stanford University)
3. David P. Woodruff (IBM)
4. Qin Zhang (Indiana University)

BibTeX Citation

@inproceedings{gucht_pods15,
        address = {New York, NY, USA},
        series = {{PODS} '15},
        title = {{The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication}},
        url = {https://dl.acm.org/doi/10.1145/2745754.2745779},
        doi = {10.1145/2745754.2745779},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Van Gucht, Dirk and Williams, Ryan and Woodruff, David P. and Zhang, Qin},
        year = {2015}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,573	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7431378e-05
8,101	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	5.3917406e-05
8,443	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3324907e-05
8,822	Bias-Aware Sketches	2017	VLDB	5.2692495e-05
9,420	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1802184e-05
12,200	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9769913e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
168	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00027151132
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020001237
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017379171
799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00013882649
866	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013381756
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011697392
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010129129
1,619	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010052059
1,934	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.341845e-05
3,785	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	7.0192685e-05
7,327	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	5.549772e-05
7,900	On the complexity of division and set joins in the relational algebra	2005	PODS	5.4292541e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,045	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS
2	5,456	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB
3	6,151	Similarity Join over Array Data	2016	SIGMOD
4	12,389	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
5	2,802	Distributed Join Algorithms on Thousands of Cores	2017	VLDB
6	4,275	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB
7	8,623	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS
8	7,266	Submodularity of Distributed Join Computation	2018	SIGMOD
9	11,486	Topology-aware Parallel Joins	2024	PODS
10	12,200	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS