Let $A$ be a finite set, and $S \subset \mathcal{P}(A)$.
Is there a data structure for $S$ that would allow to quickly retrieve an element $q \in S $, given a key $p \in \mathcal{P}(A)$, such that $q$ is (one of) the smallest superset(s) of $p$?
The assumption is that $A$ is relatively small and that the elements in $S$ and $\mathcal{P}(A)$ are represented with binary integers, which fit within single memory words. This allows to determine their size, subset relationship, and hash values in $\mathcal{O}(1)$ time.



Your Answer

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