I have $k$ sets of similar sizes, that cover a universe $U$.
e.g. for $k=3$ and $U = \{1, 2, 3, 4, 5, 6\}$:
$S_0 = \{1, 2, 4\}$
$S_1 = \{2, 3, 4\}$
$S_2 = \{4, 5, 6\}$
I have another larger set $C$ guaranteed to be subset of $U$.
$C \subseteq \bigcup\limits_{i=0}^{k} s_{i}$.
e.g. $C = \{1, 2, 3, 4, 5\}$
I want to be able to verify whether $C$ and $U$ are equal or not.
Is there a distributed streaming algorithm that has a minimal space complexity with an acceptable false positive rate?
- Sets $S_i$ are distributed on independent nodes, they need to be processed independently.
- $C$ is local.
An ideal solution would process the subsets $S_0,S_1, .. S_k$ in a single pass and create a sketch or a summary structure which then could be combined to verify against $C$. $C$ can be processed in multiple passes.
My thoughts towards a solution:
I thought of using an $n$-bit hashing algorithm. After hashing every element I could mark them on a bitset of size $2^n$. OR'ing these bitsets would give me the bitset of their union. Therefore I can calculate these bitsets once per $S_i$, collect these bitsets, OR them to compare against the bitset of $C$.
I'm not sure if there's a better solution than this (or even if this is a good solution or not). I can't really tell what would the false positive rate be, but I can tell it will be smaller as $n$ grows (at the exponential expense of bitset space).
Note: I had asked a similar question earlier: Fingerprint functions for set equality checks?. I realized later on, the actual problem I'm trying to solve is the special case of that problem. Here the larger set $C$ is guaranteed to be a subset of the union of all smaller sets $S_0, S_1, .. S_k$.
