A subset lookup algorithm

Question

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

Answer 1

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

Answer 2

Perhaps you can use an "information retrieval" technique: in the preprocessing phase, build an 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.