1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – mike
    Commented Mar 20, 2021 at 14:29
  • $\begingroup$ 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). $\endgroup$
    – Ariel
    Commented Mar 20, 2021 at 14:36
  • $\begingroup$ by "remembers all elements" you meant all non-duplicate (unique)elements ? $\endgroup$
    – mike
    Commented Mar 20, 2021 at 14:53
  • $\begingroup$ 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. $\endgroup$
    – Ariel
    Commented Mar 20, 2021 at 14:54
  • $\begingroup$ 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\}$. $\endgroup$
    – mike
    Commented Mar 20, 2021 at 14:58

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.