Set Intersection

Given sets $S_1, \dots, S_N\subseteq [U]$ each of size at most $s$ and a set of $q$ queries $Q\subseteq [N]^2$ , report for each query $(i, j)\in Q$ the set $S_i\cap S_j$ . Occasionally we specify a size threshold up to which the algorithm is supposed to list elements.

Parameters

$|U|$ : size of universe
$N$ : number of sets
$s$ : bound on size of each set
$q$ : number of queries
$r$ : size threshold (for listing elements)

Related Problems

Set Intersection

Set Disjointness

Insufficient data to display graph

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Insuffient Data to display table

Reductions Table

Displaying 2 of 2 reductions

Other relevant algorithms

Insuffient Data to display table