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.2746158e-05
Overall Rank: 5,905 | 58.97%
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,415	An Optimal Algorithm for l1-Heavy Hitters in Insertion Streams and Related Problems	2016	PODS	5.064828e-05
7,503	Space Lower Bounds for Itemset Frequency Sketches	2016	PODS	4.7135369e-05
7,952	Efficient Matrix Sketching over Distributed Data	2017	PODS	4.6089395e-05
8,586	Bias-Aware Sketches	2017	VLDB	4.4855966e-05
9,743	Output-Sensitive Evaluation of Regular Path Queries	2025	PODS	4.2856385e-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
264	Efficient Exact Set-Similarity Joins	2006	VLDB	0.00029950264
442	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00023095823
449	An Optimal Algorithm for the Distinct Elements Problem	2010	PODS	0.00022914472
962	A Comparison of Join Algorithms for Log Processing in MapReduce	2010	SIGMOD	0.00015003834
1,043	Set Containment Joins: The Good, The Bad and The Ugly	2000	VLDB	0.00014468616
1,073	Processing Theta-Joins using MapReduce*	2011	SIGMOD	0.00014255717
1,559	Evaluation of Main Memory Join Algorithms for Joins with Subset Join Predicates	1997	VLDB	0.00011368746
1,757	Efficient Processing of Joins on Set-valued Attributes	2003	SIGMOD	0.00010659352
2,588	Pass-Join: A Partition-based Method for Similarity Joins	2012	VLDB	8.4872437e-05
3,678	Providing Better Support for a Class of Decision Support Queries	1996	SIGMOD	6.8482668e-05
7,075	Optimizing Queries with Universal Quantification in Object-Oriented and Object-Relational Databases	1997	VLDB	4.8371887e-05
7,722	On the complexity of division and set joins in the relational algebra	2005	PODS	4.6628934e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.00012118832
2,856	A Worst-Case Optimal Multi-Round Algorithm for Parallel Computation of Conjunctive Queries	2017	PODS	8.0120856e-05
4,855	Distributed Transitive Closure Computations: The Disconnection Set Approach	1990	VLDB	5.8698466e-05
6,502	Similarity Join over Array Data	2016	SIGMOD	5.0288901e-05
11,898	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR	4.1905499e-05
3,428	Distributed Join Algorithms on Thousands of Cores	2017	VLDB	7.1002401e-05
4,752	Set Similarity Joins on MapReduce: An Experimental Survey	2018	VLDB	5.9396804e-05
8,213	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5533861e-05
7,154	Submodularity of Distributed Join Computation	2018	SIGMOD	4.8107765e-05
10,915	Topology-aware Parallel Joins	2024	PODS	4.1905499e-05