<p>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. </p>

<p>The most relevant paper is one by Charikar, Indyk and Panigrahy from ICALP 2002: 
<a href="http://dl.acm.org/citation.cfm?id=684567" rel="nofollow">New Algorithms for Subset Query, Partial Match, Orthogonal Range Searching, and Related Problems</a></p>

<p>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 <a href="http://en.wikipedia.org/wiki/Inverted_index" rel="nofollow">inverted index</a>.</p>

CC BY-SA 3.0
2013-11-04T06:54:20.187Z
My database it pretty large, and the alphabeth is extreamly large, making an inverse index out of the question.
Martin Kristiansen
CC BY-SA 3.0
2013-11-04T06:27:20.850Z
2013-11-04T06:27:20.850Z
Suresh Venkat
<p>Let <span class="math-container">$s = \{\sigma_1, \sigma_2 \ldots \sigma_n\}$</span>, where <span class="math-container">$\sigma_i \in \Sigma$</span>, denote a set of alphabet characters.</p>
<p>And <span class="math-container">$s \in S$</span> where <span class="math-container">$S$</span> denotes a set of sets.</p>
<p>Given a new set <span class="math-container">$s' = \{\sigma'_1, \sigma'_2, \ldots \sigma'_n \}$</span> is there an efficient algorithm for getting all sets, <span class="math-container">$s'' \in S$</span>, where <span class="math-container">$s' \subset s''$</span></p>
<p>In other words, given a set of sets, is there a way of getting the subset of sets the contain specific set of attributes?</p>
<p>I would be willing to build data structures with search and update complexities in the <span class="math-container">$O(\log (n))$</span> range, <span class="math-container">$n$</span> being the number of sets - also I would like the alphabet <span class="math-container">$\Sigma$</span> to be infinite.</p>
<p>The alphabet size is not known in advance.</p>
<p>This seems like a pretty simple problem, I am however not able to get my head around it.</p>
<h2><strong>Example:</strong></h2>
<p>Given the dataset <span class="math-container">$S$</span>:</p>
<blockquote>
<p><span class="math-container">$s_1$</span>: {a,b,c,d}</p>
<p><span class="math-container">$s_2$</span>: {a,c,d}</p>
<p><span class="math-container">$s_3$</span>: {b,c,d,f}</p>
<p><span class="math-container">$s_4$</span>: {a,b,d,h}</p>
</blockquote>
<p>and the query string <span class="math-container">$s'$</span> = <code>{a,b}</code></p>
<p>I would like the result :</p>
<blockquote>
<p><span class="math-container">$s_1$</span>: {a,b,c,d}</p>
<p><span class="math-container">$s_4$</span>: {a,b,d,h}</p>
</blockquote>
<p>The only sets containing the two elements.</p>

CC BY-SA 3.0
2013-11-04T05:13:16.723Z
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.
CC BY-SA 3.0
2013-11-04T05:33:02.920Z
@D.W. I've removed even more of my sigmas
Martin Kristiansen
<regular-language><regular-expressions>
Finding containing sets, within sets of sets
Martin Kristiansen
# Finding containing sets, within sets of sets

(Asked by: username_0 on 2013-11-03)

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.

**Tags:** regular-language, regular-expressions
> **Comments:**
> **username_1**: 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''$?  
> **username_0**: @D.W. I've removed even more of my sigmas  

---

## 1 answers

### Answer by username_2 on 2013-11-04. Score: 2

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](http://dl.acm.org/citation.cfm?id=684567)

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](http://en.wikipedia.org/wiki/Inverted_index).

> **Comments:**
> **username_0**: My database it pretty large, and the alphabeth is extreamly large, making an inverse index out of the question.  

---

