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