Finding containing sets, within sets of sets

Question

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.

Answer 1

The problem you are trying to solve is called PARTIAL-MATCH: given a database of sets, and a query set, find all sets in the database that contain the query.

The most relevant paper is one by Charikar, Indyk and Panigrahy from ICALP 2002: New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems

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.