5
$\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?

$\endgroup$
  • $\begingroup$ look at MinHash. Also, somewhat similar question was asked a few days ago (search for MinHash) $\endgroup$ – Bulat May 16 '19 at 10:35
3
$\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

| cite | improve this answer | |
$\endgroup$

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.