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.
