9
$\begingroup$

I am interested in finding a data structure that supports the following operations:

  • Insert Set: Insert a set into the data structure.

  • Decide Subset: Determine whether a given set is a subset of any of the inserted sets.

The most obvious way to implement this would be as a hash set of hash sets, but I think some performance gains could be had by exploiting common subsets among the stored sets. For example, if {1} and {1,2} were both stored, only {1,2} would need to be kept. Any ideas?

Improve this question
$\endgroup$
1
  • $\begingroup$ look at MinHash. Also, somewhat similar question was asked a few days ago (search for MinHash) $\endgroup$
    – Bulat
    Commented May 16, 2019 at 10:35

1 Answer 1

Reset to default
5
$\begingroup$

There is a popular algorithm in bioinformatics for solving this exact problem. I believe it is known as the multi-set membership testing problem (MSMT).

BigSI

The idea in BigSI is that you represent each of the $N$ inserted sets as a bloom filter of length $m$ with $k$ hashes. Let $Q$ be our $m\times N$ table, where the columns represent each of the $N$ bloom filters for each of our $N$ sets $\{X_1, ... , X_N\}$.

Now we wish to query $Q$ for an input set $S$. Let $A=\{h_i(s) \;\;\forall i\in[k],s\in S\}$ be all of the hash values for the input set. We have the following condition $$S\subseteq X_i \iff Q[r][i] = 1 \;\;\forall r\in A$$ It remains to find columns such that the right hand side holds true. To do this, we create a subset of the rows $Q'=\{row_i(Q) \; | i \in A\}$ . Now our condition is that $$S\subseteq X_i \iff Q'[r][i] = 1 \;\;\forall r\in [|A|]$$ i.e. any columns with all $1$s in $Q'$ is a superset of $S$. We can find such columns $C$ by performing $$ R = \bigwedge_{r\in[|A|]}Q'[r]$$ $$ C = \{i \;\;| \;\; R[i] = 1\}$$ If $C\neq \emptyset$, then $S$ must have been a subset of one of the original $N$ sets. Of course this algorithm is also able to tell you which of the original sets $S$ is a subset of. Since your question doesn't need that information, there may be some minor optimizations.

Here is a figure from the BigSI publication, where the input sets are FASTQ files which are broken down into $k$-mers. Part (a) represents the 5 input sets, each of cardinality 2. Figure (b) shows the resulting $Q$ table and the $\texttt{AND}$ operation used to find the superset inputs. Figure (c) is a naive alternative, where each row represents a possible element from one of the input sets, however this table would have to grow vertically as well as horizontally for each input set, as we may see new elements. enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ This seems to just test subset membership for each of the sets $X_i$, by using bloom filter $bloom(S) \subseteq? bloom(X_i)$. So the only optimization here compared to a naive test is replacing the test $S \subseteq? X_i$ by $bloom(S) \subseteq? bloom(X_i)$. Which maybe useful for large sets but it does not seem to focus on the problem itself, where one would hope to get a sublinear membership test (in the number of sets). $\endgroup$
    – Fractalic
    Commented Jul 1 at 8:20
  • 1
    $\begingroup$ That is a fair point. In that regard, there is RAMBO and Sequence Bloom Trees, which both perform queries in sublinear time wrt the number of sets in the index. $\endgroup$
    – Throckmorton
    Commented Jul 1 at 22:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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