Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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$, $\forall x \in I$ 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.

share|improve this question
2  
This is already somewhat $O(n)$. Building the structure will surely take longer. Though if you need to perform this operation repeatedly, have you considered a plain old trie? –  Karolis Juodelė Jan 2 '13 at 17:40
    
I would think of it as a set of strings. Use something similar to a suffix tree. (look at this: en.wikipedia.org/wiki/Generalised_suffix_tree). For instance, a tree rooted at $\emptyset$. Every node has at most 10 children. You would include a set $\{1,2,3\}$ for example starting by inserting 1 as a child of the root, 2 as a child 1 etc .. i think you can solve it efficiently with something like this, but you need to take care of details. –  AJed Jan 2 '13 at 17:41
    
@KarolisJuodelė exactly! trie is the word i was looking for. –  AJed Jan 2 '13 at 17:42
    
Are the sets inside $A$ (the set of sets) dynamic? –  Paresh Jan 2 '13 at 18:58
    
@Paresh If you have a method that takes advantage of it being $A$ being static, I'd like to hear it as long as you specify as such. I don't know what you mean about the sets in $A$ being dynamic though, that is equivalent to removing the set, and inserting another, unless I am misunderstanding the question. –  Realz Slaw Jan 2 '13 at 19:03
show 2 more comments

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.