# Best data structure for queries about subsets?

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?

• look at MinHash. Also, somewhat similar question was asked a few days ago (search for MinHash) – Bulat May 16 '19 at 10:35

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.