<p>Perhaps you can use an "information retrieval" technique: in the preprocessing phase, build an <a href="http://en.wikipedia.org/wiki/Inverted_index" rel="nofollow">inverted index</a> (in your case a simple $n \times | {\cal X}|$ bidimensional array is enough) that maps an element $x_i \in \{1,...,n\}$ to the sets in $\cal X$ that contain it: $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \} $.</p>

<p>Set up an integer array $occ$ of length $|\cal X|$.</p>

<p>Then for each $y_i \in A$ retrieve $inv(y_i)$, and for each $X_j \in inv(y_i)$ do $occ[j] = occ[j]+1$</p>

<p>At the end the sets you need are those for which $|X_j|=occ[j]$.</p>

<p>You can arbitrarily speed up the process (at the cost of exponential space) by indexing two or more elements together.</p>

CC BY-SA 3.0
2012-01-04T19:35:28.973Z
2012-01-04T19:35:28.973Z
Marzio De Biasi
<p>This is not an answer. It is a simple but long observation. I hope it will be useful.</p>

<p>The decision version of your problem is: Does $\cal X$ contain a subset of $A$?</p>

<p>This problem is related to the problem of evaluating monotone boolean functions of $n$ variables. A subset of $\{1,\ldots,n\}$ is equivalent to an $n$-bitstring, so the family $\cal X$ is equivalent to a boolean function $f$ of $n$ variables. Given a function $f$, one can define the least monotone function that is not bigger than $f$, namely $g(y)=(\exists x\subseteq y,\,f(x))$. The original problem is then reduced to evaluating $g(A)$. Conversely, the problem of evaluating a monotone boolean function can be reduced to the original problem, either naively by taking $f=g$ or by choosing an $f$ that makes $\cal X$ smaller.</p>

<p>In practice BDDs tend to work well. So one possible approach is to build the BDD for $f$, derive from it the BDD for $g$, and then evaluate $g$. The average size of the BDD for $g$ must be $\Omega\left(\binom{n}{n/2}\right)$, because <a href="http://en.wikipedia.org/wiki/Dedekind_number" rel="nofollow">there are many monotone boolean functions</a>. Hence, in theory this is a bad solution.</p>

<p>But (1) a better analysis might be possible and (2) there might be tweaks to this approach that make it better. For example, I didn't use in any way the correlation between the size of $\cal X$ and the size of $g$'s BDD. (There must be a correlation, but I don't know if it is simple or usable here.)</p>

<p>For completeness, a simple algorithm for computing the BDD for $g$ from the BDD for $f$ is the following.
$$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$$
Here $\lor$ is the standard or-operation on BDDs.</p>

CC BY-SA 3.0
2012-01-03T20:48:29.910Z
Isn't this more or less equivalent to precalculating the answer for each subset of $\{1,2,...,n\}$, caching all the results in a binary tree of size $2^n$, and then looking up the right result (in time $O(n)$) when you're given $A$?
mjqxxxx
CC BY-SA 3.0
2012-01-04T14:13:08.747Z
Using exponential space to store preprocessed data sounds like cheating to me, although it is not prohibited in the question.  But I may be biased toward the Church of Worst-Case Complexity.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-05T00:36:24.763Z
mjqxxxx and Tsuyoshi: I agree with both of you. I rewrote the text so that, I hope, it is more clear that I agree. :)
Radu GRIGore
CC BY-SA 3.0
2012-01-03T18:14:35.067Z
2012-01-04T16:08:55.500Z
2012-01-04T16:08:55.500Z
Radu GRIGore
<p>Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary.  After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. I want to identify any sets $B \in \mathcal X$ with $B \subseteq A$.</p>

<p>The obvious algorithm (without any preprocessing) takes time $O(n |\cal X|)$ -- you simply test $A$ against each $B \in \mathcal X$ separately. Is there anything better than this?</p>

<p>If it helps, you can assume that, for any $A$, the total number of matches $B \in \mathcal X$ is bounded by something like $O(1)$.</p>

<ds.algorithms><ds.data-structures>
A subset lookup algorithm
David Harris
# A subset lookup algorithm

(Asked by: username_0 on 2012-01-03)

Suppose I have a list $\cal X$ of subsets of $\{1, ..., n\}$. I can do preprocessing on this list if necessary. After this preprocessing, I am presented with another set $A \subseteq \{1, ..., n \}$. I want to identify any sets $B \in \mathcal X$ with $B \subseteq A$.

The obvious algorithm (without any preprocessing) takes time $O(n |\cal X|)$ -- you simply test $A$ against each $B \in \mathcal X$ separately. Is there anything better than this?

If it helps, you can assume that, for any $A$, the total number of matches $B \in \mathcal X$ is bounded by something like $O(1)$.

**Tags:** ds.algorithms, ds.data-structures


---

## 2 answers

### Answer by username_1 on 2012-01-04. Score: 3

Perhaps you can use an "information retrieval" technique: in the preprocessing phase, build an [inverted index](http://en.wikipedia.org/wiki/Inverted_index) (in your case a simple $n \times | {\cal X}|$ bidimensional array is enough) that maps an element $x\_i \in \{1,...,n\}$ to the sets in $\cal X$ that contain it: $inv(x\_i)= \{ X\_j \in {\cal X} \; | \; x\_i \in X\_j \} $.

Set up an integer array $occ$ of length $|\cal X|$.

Then for each $y\_i \in A$ retrieve $inv(y\_i)$, and for each $X\_j \in inv(y\_i)$ do $occ[j] = occ[j]+1$

At the end the sets you need are those for which $|X\_j|=occ[j]$.

You can arbitrarily speed up the process (at the cost of exponential space) by indexing two or more elements together.


---

### Answer by username_2 on 2012-01-03. Score: 3

This is not an answer. It is a simple but long observation. I hope it will be useful.

The decision version of your problem is: Does $\cal X$ contain a subset of $A$?

This problem is related to the problem of evaluating monotone boolean functions of $n$ variables. A subset of $\{1,\ldots,n\}$ is equivalent to an $n$-bitstring, so the family $\cal X$ is equivalent to a boolean function $f$ of $n$ variables. Given a function $f$, one can define the least monotone function that is not bigger than $f$, namely $g(y)=(\exists x\subseteq y,\,f(x))$. The original problem is then reduced to evaluating $g(A)$. Conversely, the problem of evaluating a monotone boolean function can be reduced to the original problem, either naively by taking $f=g$ or by choosing an $f$ that makes $\cal X$ smaller.

In practice BDDs tend to work well. So one possible approach is to build the BDD for $f$, derive from it the BDD for $g$, and then evaluate $g$. The average size of the BDD for $g$ must be $\Omega\left(\binom{n}{n/2}\right)$, because [there are many monotone boolean functions](http://en.wikipedia.org/wiki/Dedekind_number). Hence, in theory this is a bad solution.

But (1) a better analysis might be possible and (2) there might be tweaks to this approach that make it better. For example, I didn't use in any way the correlation between the size of $\cal X$ and the size of $g$'s BDD. (There must be a correlation, but I don't know if it is simple or usable here.)

For completeness, a simple algorithm for computing the BDD for $g$ from the BDD for $f$ is the following.
$$m(x?f\_1:f\_0)=x?(m(f\_0)\lor m(f\_1)):m(f\_0)$$
Here $\lor$ is the standard or-operation on BDDs.

> **Comments:**
> **username_3**: Isn't this more or less equivalent to precalculating the answer for each subset of $\{1,2,...,n\}$, caching all the results in a binary tree of size $2^n$, and then looking up the right result (in time $O(n)$) when you're given $A$?  
> **username_4**: Using exponential space to store preprocessed data sounds like cheating to me, although it is not prohibited in the question.  But I may be biased toward the Church of Worst-Case Complexity.  
> **username_2**: username_3 and Tsuyoshi: I agree with both of you. I rewrote the text so that, I hope, it is more clear that I agree. :)  

---

