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.8800995e-05
Overall Rank: 6,121 | 58.85%
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,570	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.7458578e-05
8,094	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	5.3942942e-05
8,434	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.3350162e-05
8,815	Bias-Aware Sketches	2017	VLDB	5.2708103e-05
9,410	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.1826718e-05
12,194	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	4.9793485e-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.00027163517
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020009936
494	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017387321
799	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00013889081
865	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.0001338765
1,171	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011702886
1,594	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00010133792
1,618	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010056773
1,933	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.3459285e-05
3,783	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	7.0225701e-05
7,324	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	5.5523996e-05
7,896	On the complexity of division and set joins in the relational algebra	2005	PODS	5.4318255e-05

Semantically Similar Papers

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