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: 1663
Venue: PODS
Year: 2015
Pagerank: 6.0150613e-05
Overall Rank: 5,996 | 58.87%
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,454	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.8746921e-05
7,926	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	5.5181056e-05
8,268	Efficient Matrix Sketching over Distributed Data	2017	PODS	5.4574671e-05
8,653	Bias-Aware Sketches	2017	VLDB	5.3914428e-05
9,235	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	5.3016261e-05
11,894	Distributed Statistical Estimation of Matrix Products with Applications	2018	PODS	5.093636e-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
169	Efficient Exact Set-Similarity Joins	2006	VLDB	0.0002743469
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
482	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00017772185
769	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00014166872
843	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00013666161
1,151	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00011938186
1,568	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.0001034191
1,592	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010253457
1,886	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	9.5358137e-05
3,708	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	7.1814701e-05
7,183	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	5.6793385e-05
7,732	On the complexity of division and set joins in the relational algebra	2005	PODS	5.5564984e-05

Semantically Similar Papers

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