How much memory is needed for counting distinct elements in a stream exactly with high probability

Question

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.

Answer 1

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.