# Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Suppose there is an n-element stream with elements from $$\{0,1\}^\ell$$ which means each element is in set $$\{0, \dots , 2^\ell-1\}$$. Also may assume $$2^\ell >n^2$$. How can I with $$2p$$ passes over the data (for $$p \in \{1, \dots , 2^\ell\}$$) solve the number of distinct elements problem using only $$O(\frac{n}{p}\ell)$$ bits of memory? Not looking for probabilistic algorithms.

Try something along the following lines. Preform $$p$$ iterations where each iteration consists of two passes over the stream. The $$i$$'th iteration first pass remembers all elements whose index $$\bmod p$$ equals $$i$$ , denote this collection by $$S_i$$. The second pass, for each element of the stream whose index $$\bmod p$$ is greater than $$i$$, checks if it appears in $$S_i$$, and if so deletes it. Denote by $$S_i'$$ the remaining subset after the second pass, then your algorithm returns $$\sum\limits_{i=1}^p |S_i'|$$.

• thanks but it do not work. at last round there is no $index \mod p$ which is greater thatn $i$. consider case when $p=2$ at last round (second iteration)$i=1$ and we are looking for elements which $index \mod 2 > 1$.
– mike
Commented Mar 20, 2021 at 14:29
• This just means that $|S_{p-1}'|=|S_{p-1}|$ (we want to count all the unique elements whose index mod $p$ is $p-1$, since they were not counted in any earlier iteration). Commented Mar 20, 2021 at 14:36
• by "remembers all elements" you meant all non-duplicate (unique)elements ?
– mike
Commented Mar 20, 2021 at 14:53
• No, I meant keep all elements in memory (which you can do, as there are $n/p$ of those). After each iteration you only keep the size of $|S_i|'$, so you can reuse memory in the next iteration. To compute the size of $S_i$' you will have to find duplicates, luckily this doesn't require further information from the stream. Commented Mar 20, 2021 at 14:54
• am i doing this right ? for stream $\{1,1,2,1,1,2,3\}$ at iteration one we have $S_0=\{1,2,1,3\}$ and $S'_0 = \{3\}$. for second iteration $S_1=\{1,1,2\}$ and $S'_1 = \{1,1,2\}$.
– mike
Commented Mar 20, 2021 at 14:58