<p>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 <a href="http://theory.cs.princeton.edu/complexity/ipchap.pdf" rel="nofollow noreferrer">Arora-Barak book</a>).
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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-02-09T08:43:42.760Z
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.
R B
CC BY-SA 3.0
2017-02-07T21:48:41.053Z
2017-02-07T22:04:00.200Z
2017-02-07T22:04:00.200Z
domotorp
<p>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.</p>

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

<p>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.</p>

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

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

<p>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?</p>

<hr>

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

<p>In the paper <a href="http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf" rel="nofollow noreferrer">An Optimal Algorithm for the Distinct Elements Problem</a>, 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.</p>

<p>However, setting $\gamma&lt;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.</p>

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

CC BY-SA 3.0
2017-02-07T12:17:49.900Z
@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$.
R B
CC BY-SA 3.0
2017-02-08T04:07:14.727Z
Have you looked literature on streaming lower bounds?
Chandra Chekuri
CC BY-SA 3.0
2017-02-09T08:38:02.017Z
@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.
R B
<ds.algorithms><lower-bounds><data-streams>
How much memory is needed for counting distinct elements in a stream exactly with high probability
R B
# How much memory is needed for counting distinct elements in a stream exactly with high probability

(Asked by: username_0 on 2017-02-07)

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](http://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf), 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

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

**Tags:** ds.algorithms, lower-bounds, data-streams
> **Comments:**
> **username_0**: @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$.  
> **username_1**: Have you looked literature on streaming lower bounds?  
> **username_0**: @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.  

---

## 1 answers

### Answer by username_2 on 2017-02-07. Score: 3

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](http://theory.cs.princeton.edu/complexity/ipchap.pdf)).
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.

> **Comments:**
> **username_0**: 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.  

---

