# Find $k$ subsets containing a particular element quickly

Suppose there are $n$ subsets of $U$. I want to quickly (in terms of average-case) find k $(< n)$ subsets that contain $e \in U$ (call this Extraction(e)). Elements are integers.

To that effect, I want to preprocess/encode the $n$ subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is (assume that this item is uniformly selected over queries).

I don't have a good intuition for various methods to do this and after how much prerocessing space/time diminishing returns kick in. I'm certainly looking for something that takes polynomial time/space.

I was thinking about encoding the subsets as hashsets and then hashing together $q$ of these subsets together at a time, so that I end up with $\lceil\frac{n}{q}\rceil$ packaged hashsets. $q$ would be inferred in some fashion from the frequency distribution of all elements in U. Then I could iterate over these packaged hashsets and check for containment of $e$ in constant time (average-case).

Is this problem well-studied?

## 1 Answer

Use a hash table, keyed on elements of $U$. For each subset $S$ of $U$, say $S=\{x_1,\dots,x_\ell\}$, you'll add $S$ to the hash table $\ell$ times, once for key $x_1$, once for key $x_2$, and so on. Now to find all subsets containing some element $e$, just look into the corresponding bucket in the hash table and you can iterate over sets containing $e$ very rapidly.

This is basically just applying the idea of "indexes" from databases to your problem. It is straightforward and provides excellent time complexity, at the cost of modest space complexity (approximately doubling the space needed to store all of the subsets).