# Finding containing sets, within sets of sets

Let $$s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$$, where $$\sigma_i \in \Sigma$$, denote a set of alphabet characters.

And $$s \in S$$ where $$S$$ denotes a set of sets.

Given a new set $$s' = \{\sigma'_1, \sigma'_2, \ldots \sigma'_n \}$$ is there an efficient algorithm for getting all sets, $$s'' \in S$$, where $$s' \subset s''$$

In other words, given a set of sets, is there a way of getting the subset of sets the contain specific set of attributes?

I would be willing to build data structures with search and update complexities in the $$O(\log (n))$$ range, $$n$$ being the number of sets - also I would like the alphabet $$\Sigma$$ to be infinite.

The alphabet size is not known in advance.

This seems like a pretty simple problem, I am however not able to get my head around it.

## Example:

Given the dataset $$S$$:

$$s_1$$: {a,b,c,d}

$$s_2$$: {a,c,d}

$$s_3$$: {b,c,d,f}

$$s_4$$: {a,b,d,h}

and the query string $$s'$$ = {a,b}

I would like the result :

$$s_1$$: {a,b,c,d}

$$s_4$$: {a,b,d,h}

The only sets containing the two elements.

• What do $\sigma''_i$ represent? What is their definition? Are they defined to be an enumeration of the elements of $s''$? What do you mean by $\{\sigma''_1,\dots,\sigma''\} \in s'$? That doesn't type-check (the left-hand side is a set of characters, the right-hand side is a set of characters, so the LHS can't be an element of the RHS). Do you mean that you're looking for an efficient algorithm to find all sets $s'' \in S$ such that $s' \subseteq s''$? – D.W. Nov 4 '13 at 5:13
• @D.W. I've removed even more of my sigmas – Martin Kristiansen Nov 4 '13 at 5:33

That's on the theoretical side. In practice, many simplifications can be made if one knows something about the sets and the query. For example if $|Q|$ is small, you might be able to get away with an inverted index.