Tweeted twitter.com/#!/StackCompSci/status/464885302642102272
added 59 characters in body
Source Link

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?

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). Elements are integers.

To that effect, I want to preprocess the subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is.

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?

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?

Source Link

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). Elements are integers.

To that effect, I want to preprocess the subsets so that this extraction operation can occur relatively quickly, regardless of what $e$ is.

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?