<p>The count-distinct problem is: given a stream of elements <span class="math-container">$x_1, \dots, x_n$</span> which contains duplicates, find the number of distinct elements using a small amount of space.</p>
<p>I also want the following property: given two or more streams <span class="math-container">$S_1, \dots, S_k$</span> we see the streams one after the other. After we see the streams, we are given two streams at random <span class="math-container">$S_i$</span> and <span class="math-container">$S_j$</span> and asked to return the number of unique elements in <span class="math-container">$S_i \setminus S_j$</span>. We would like to solve this problem using as small amount of memory as possible; notably we cannot afford to remember all the elements in all the streams before the query of <span class="math-container">$S_i \setminus S_j$</span>.</p>
<p>This problem can be solved using the HyperLogLog algorithm. However, this algorithm really only works when <span class="math-container">$|S_i|$</span> for all <span class="math-container">$i$</span> are about the same length. This is because the error probability is given by <span class="math-container">$O(1/\sqrt{m})$</span> where <span class="math-container">$m$</span> is the amount of memory used to store the hash values of the HyperLogLog algorithm. Suppose we care about small space <span class="math-container">$m = \log(n)$</span> where <span class="math-container">$n = \max_{S_i} (|S_i|)$</span>. Then, suppose the query asks for <span class="math-container">$S_i$</span> and <span class="math-container">$S_j$</span> where <span class="math-container">$|S_i| &lt; (1/\sqrt{\log n}) |S_j|$</span>. In this case, we would <em>not</em> achieve a good error bound on <span class="math-container">$|S_i \setminus S_j|$</span> (by the inclusion-exclusion principle <span class="math-container">$|S_i \setminus S_j| = |S_i \cup S_j| - |S_j|$</span>) since the error bound on <span class="math-container">$S_j$</span> could mask the number of elements in <span class="math-container">$S_i$</span>.</p>
<p>Are there any other existing data structures that can handle this when the sizes of <span class="math-container">$S_i$</span> differ by more than a <span class="math-container">$(1/\sqrt{m})$</span>-factor? Please do comment if any part of this question is unclear.</p>

CC BY-SA 4.0
2020-09-23T06:08:47.233Z
Suppose $|S_1| = n$ and $|S_2| = 1$ and we always want to know $|S_2 \setminus S_1| $. This appears easier than your problem, but any multiplicative approximation here would solve element in set containment, which should have some communication complexity lower bounds against it? Or am i missing some part of the problem definition
daniello
CC BY-SA 4.0
2020-09-23T06:19:48.653Z
The communication complexity lower bound i was thinking of was the one way communication complexity of the index problem.
daniello
CC BY-SA 4.0
2020-09-29T21:57:01.487Z
What is the meaning of $S_i \setminus S_j$? One can use linear sketching algorithms for distinct elements problem to answer certain questions even when there are deletions. These are more advanced techniques than Hyperloglog which works when there are not deletions.
Chandra Chekuri
<streaming-algorithms><streaming>
Estimating the cardinality of multisets given some sets of different sizes
user1246462
# Estimating the cardinality of multisets given some sets of different sizes

(Asked by: username_0 on 2020-08-26)

The count-distinct problem is: given a stream of elements $x\_1, \dots, x\_n$ which contains duplicates, find the number of distinct elements using a small amount of space.

I also want the following property: given two or more streams $S\_1, \dots, S\_k$ we see the streams one after the other. After we see the streams, we are given two streams at random $S\_i$ and $S\_j$ and asked to return the number of unique elements in $S\_i \setminus S\_j$. We would like to solve this problem using as small amount of memory as possible; notably we cannot afford to remember all the elements in all the streams before the query of $S\_i \setminus S\_j$.

This problem can be solved using the HyperLogLog algorithm. However, this algorithm really only works when $|S\_i|$ for all $i$ are about the same length. This is because the error probability is given by $O(1/\sqrt{m})$ where $m$ is the amount of memory used to store the hash values of the HyperLogLog algorithm. Suppose we care about small space $m = \log(n)$ where $n = \max\_{S\_i} (|S\_i|)$. Then, suppose the query asks for $S\_i$ and $S\_j$ where $|S\_i| < (1/\sqrt{\log n}) |S\_j|$. In this case, we would *not* achieve a good error bound on $|S\_i \setminus S\_j|$ (by the inclusion-exclusion principle $|S\_i \setminus S\_j| = |S\_i \cup S\_j| - |S\_j|$) since the error bound on $S\_j$ could mask the number of elements in $S\_i$.

Are there any other existing data structures that can handle this when the sizes of $S\_i$ differ by more than a $(1/\sqrt{m})$-factor? Please do comment if any part of this question is unclear.

**Tags:** streaming-algorithms, streaming

> **Comments:**
> **username_1**: Suppose $|S_1| = n$ and $|S_2| = 1$ and we always want to know $|S_2 \setminus S_1| $. This appears easier than your problem, but any multiplicative approximation here would solve element in set containment, which should have some communication complexity lower bounds against it? Or am i missing some part of the problem definition  
> **username_1**: The communication complexity lower bound i was thinking of was the one way communication complexity of the index problem.  
> **username_2**: What is the meaning of $S_i \setminus S_j$? One can use linear sketching algorithms for distinct elements problem to answer certain questions even when there are deletions. These are more advanced techniques than Hyperloglog which works when there are not deletions.  

---

## 0 answers

