7
$\begingroup$

Assume we know a parameter $n\in\mathbb N$, and then get to observe a sequence of elements $x_1,\ldots, x_n$, one at a time.

Our goal is to count the number of distinct elements in $x_1,\ldots, x_n$, and succeed with probability $1-\epsilon$.

A simple approach would be to compute a $\log\left({n\choose 2}\epsilon^{-1}\right)$ bits fingerprint of each element, and then count the number of distinct fingerprints.

Since the number of distinct elements is a most $n$, with probability of at least $1-\epsilon$, all fingerprints of distinct elements will be different.

This gives us a total of $\approx n\log (n^2\epsilon^{-1})-n$ bits of space.

But is this anywhere close to optimal? Can we perhaps use only $O(n\log\epsilon^{-1})$ bits for the problem? What would be a lower bound for this problem?


EDIT: I'm specifically interested in computing the number of distinct elements exactly, with high probability, and not in approximation algorithms.

In the paper An Optimal Algorithm for the Distinct Elements Problem, the authors give a $O(\gamma^{-2}+\log n)$ bits algorithm for computing a $(1+\gamma)$ approximation with high probability, and claim that this is optimal.

However, setting $\gamma<n^{-1}$ for getting exact count with high probability gives a $\Omega(n^2)$ bits algorithm, which seems worse than the $O(n\log n)$ proposed above.

They do not assume that $n$ is known in advance, which may explain this difference.

$\endgroup$
  • $\begingroup$ I'm pretty sure that even for ​ n = 2 ​ and ​ $\epsilon$ = 1/3 , ​ the amount of memory needs to depend on $\hspace{.84 in}$ the size of the universe (from which $x_{\hspace{.02 in}1}$ and $x_{\hspace{.03 in}2}$ are chosen). ​ ​ ​ ​ $\endgroup$ – user6973 Feb 7 '17 at 12:10
  • 1
    $\begingroup$ @RickyDemer - I assume that we have access to hash function $h:\mathcal U\to \{0,1\}^\infty$ that can map universe elements to random bit string of arbitrary length (and it is i.i.d for different elements). My ``fingerprints'' are simply the first bits of $h(x)$ for each element $x$. $\endgroup$ – R B Feb 7 '17 at 12:17
  • $\begingroup$ Have you looked literature on streaming lower bounds? $\endgroup$ – Chandra Chekuri Feb 8 '17 at 4:07
  • $\begingroup$ @ChandraChekuri - see my edit above, it seems that the streaming lower bound known does not assume that the stream length is known in advance, and doesn't seem to be lower than simply keeping the elements fingerprints when exact counting is needed. $\endgroup$ – R B Feb 9 '17 at 8:38
3
$\begingroup$

You can do $O(\log \frac n\epsilon)$ space if you only want an approximation. The main idea is that you use the random hash function $h$ to do the same protocol as in the Goldwasser-Sipser Set Lowerbound (which you can find, e.g., in the Arora-Barak book). So you pick a target $y$ and observe whether $h(x_i)$ holds for any $i$. If the sequence is diverse, then whp. you can find such a $i$, otherwise you cannot. To increase the probability of success, you can pick $O(\log \frac 1\epsilon)$ different $y$'s of length $O(\log n)$ and do the protocol for each.

If you want an exact answer, then more precise calculations are needed. I think $O(polylog \frac n\epsilon)$ space might be still enough, but I might be wrong.

$\endgroup$
  • $\begingroup$ Thank for the answer ! However, I'm specifically interested in exact answer. I believe you are right about a polylog bits being the right bound. $\endgroup$ – R B Feb 9 '17 at 8:43

Your Answer

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

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