6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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 $\endgroup$
    – daniello
    Sep 23, 2020 at 6:08
  • $\begingroup$ The communication complexity lower bound i was thinking of was the one way communication complexity of the index problem. $\endgroup$
    – daniello
    Sep 23, 2020 at 6:19
  • $\begingroup$ 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. $\endgroup$ Sep 29, 2020 at 21:57

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.