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$.

  • 1
    $\begingroup$ This is not a streaming algorithm, but uses a gossip model, so it may be useful: arxiv.org/abs/1904.10706 . The main idea is to rephrase the problem as an LP-type problem, and use a distributed version of Clarksons algorithm (which is a Las Vegas algorithm). $\endgroup$
    – Discrete lizard
    Jan 30, 2022 at 12:37


Your Answer

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