Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $I\subset \mathbb Z$, find $C$, the sets in $A$ that include all of $I$, that is $C=\left\{ B \in A \mid I\subseteq B\right\}$.
Looking for the best of a few solutions.
The right approach will generally tend to depend on your data -- size of sets, number of sets, range of elements, size of input, number of queries etc. Here are a couple of approaches:
Approach 1: You could use a Bloom filter for each of the sets in $A$, and for the input set $I$. Assuming the same number of bits for each set, and the same $k$ hash functions for each bloom filter, you could do a bitwise AND of two filters to do a probabilistic test for subsets. This will give no false negatives, but may give false positives. For example, let $F_I$ and $F_{A_i}$ be the bit-arrays of the Bloom Filters for the input set $I$ and some set $A_i$ in $A$. Then, if $F_{A_i} \cdot F_I = F_I$, then there is a possibility that $I \subseteq A_i$. If they are not equal, then $A_i$ definitely does not contain $I$. Using 64 bit integers, you can quickly perform bitwise AND, and comparison operations on a large number of bits, and so can quickly eliminate sets which do not contain $I$. If they turn out to be equal, then for confirmation, you might then have to check each element of $I$ for presence in $A_i$, where $A_i$ might be a hash set.
One downside of Bloom filters is that addition of elements to the set increases the probability of false positives, and deletion of elements is not possible (in simple implementations) since they introduce false negatives. So for deletion of some integer from a set in $A$, the corresponding Bloom filter will have to be recreated. Also, this method will generally give best results when the size of sets is large enough that querying from hash sets starts becoming slow.
Approach 2: If the number of sets is fairly large, but the data distribution is such that there are relatively few unique integers (what is relatively few will depend on your implementation and requirements), you could store the unique integers instead of the sets. You could have a hash-map where each integer is the key, and the value contains a bit-vector (or list) of the sets to which the integer belongs to. Then, you check each integer of $I$ for presence in the hash-map. If it is not found in the hash-map ($O(1)$), then no set of $A$ contains $I$. Otherwise, keep taking the intersection of the sets associated with the integer being checked, with the sets so far found that contain all elements checked thus far. Thus, the problem boils down to efficient set intersection. If the list of sets in the hash map is a bit vector, you need to perform bitwise AND. If they are a list (say, sorted), you can use an adaptation of merge-sort.
