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