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: 1664
Venue: PODS
Year: 2015
Pagerank: 5.2796864e-05
Overall Rank: 5,902 | 58.95%
DOI: 10.1145/2745754.2745779

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
6,418	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.0696932e-05
7,504	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	4.7180617e-05
7,949	Efficient Matrix Sketching over Distributed Data	2017	PODS	4.613363e-05
8,599	Bias-Aware Sketches	2017	VLDB	4.4879268e-05
9,744	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2897489e-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
266	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029718727
383	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00024820873
447	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00022900171
960	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00015012242
1,048	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00014457009
1,074	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014260096
1,562	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011356744
1,763	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010638276
2,592	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4795761e-05
3,676	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	6.8547125e-05
7,079	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	4.8418318e-05
7,724	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6673705e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
2,849	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0195487e-05
6,507	Similarity Join over Array Data	2016	SIGMOD	5.0337166e-05
4,852	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8764777e-05
11,890	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR	4.1945683e-05
3,443	Distributed Join Algorithms on Thousands of Cores	2017	VLDB	7.0887214e-05
4,775	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	5.9315784e-05
8,215	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5577562e-05
7,153	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8153963e-05
10,911	Topology-aware Parallel Joins	2024	PODS	4.1945683e-05