Back to papers

On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms

Summary: Dynamic index for equi-joins using Õ(IN) space and O(1) updates, returning a uniform join sample in Õ(IN^{rho*}/max{1,OUT}) time w.h.p., where rho* is the fractional edge covering number. Shows that under the combinatorial k-clique hypothesis no combinatorial algorithm can output the full join in O(IN^{rho*−ε}) w.h.p. even when OUT ≤ IN^{ε}, thereby justifying the O(IN^{rho*}) worst-case optimal bound. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID

1885

Venue

PODS

Year

2023

Pagerank

5.8184457e-05

Overall Rank

4,926 | 65.77%

DOI

10.1145/3584372.3588666