2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.