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.


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.

  • $\begingroup$ 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''$? $\endgroup$ – D.W. Nov 4 '13 at 5:13
  • $\begingroup$ @D.W. I've removed even more of my sigmas $\endgroup$ – Martin Kristiansen Nov 4 '13 at 5:33

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.

  • $\begingroup$ My database it pretty large, and the alphabeth is extreamly large, making an inverse index out of the question. $\endgroup$ – Martin Kristiansen Nov 4 '13 at 6:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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