The Number of Distinct Elements

Problem

In many applications, data comes as a stream $S = \{x_1, x_2, ..., x_n \}$ , where each $x_i, i \in [n]$ belongs to the domain $\mathcal{U}$ , with size $|\mathcal{U}| = N$ . With out lost of generality, suppose each element in $\mathcal{U}$ appear at least once in $S$ .

Problem. Estimate $N$ , i.e., the number of distinct elements in $S$ .

Naive solutions include

Sorting. With quicksort, this can be preformed in $O(n \log n)$ expected time and $O(n)$ space.
Hashing. With hashing (e.g., Cuckoo hashing), this can be done in $O(n)$ time and $O(n)$ space with two level hashing.

In real world application, $n$ could be extremely large. Therefore, the demand for $O(n)$ space is expansive or even impossible.

Question. Can we perform this with $\tilde O(1)$ space?

If we allow some error, this is possible.

Flajolet and Martin Algorithm

Let $\mathcal{H}$ be the collection of all functions from $\mathcal{U}$ to $[0, 1]$ . Suppose that we pick a function $h$ uniformly at randomly from $\mathcal{H}$ , then it maps elements in $\mathcal{U}$ independently and uniformly at random to real numbers in $[0, 1]$ .

Question: can we find another family of $\mathcal{U}$ so that the following analysis still hold?

The algorithm works as follows.

Flajolet and Martin Algorithm.

Denote $h(S) = \{ h(x_1), h(x_2), ..., h(x_n)\}$ ;

Let $Z \leftarrow \min h(S)$ ;

Return $1 / Z - 1$ .

Expectation

Observation. $\Pr [ Z \ge z] = (1 - z)^N$ and $\Pr[Z \le z] = 1 - (1 - z)^N$ .

Hence the density function is given as follows.

Density Function. Let $p$ be the density function of $Z$ , then
$p(z) = \frac{\partial \Pr[Z \le z] }{ \partial z} = N (1 - z)^{N - 1}.$

We are ready to discuss the expectation.

Theorem. $\mathbb{E} [Z] = 1 / \big(N + 1\big)$ .

Proof 1.

\mathbb{E} [Z] = \int_{z = 0}^1 z \cdot p(z) \ dz = \frac{1}{N + 1}.

$\square$

Proof 2. Another way to prove this is to introduce an additional element $x_{n + 1}$ which is different from any other element in $\mathcal{U}$ and let $S' = S \cup \{ x_{n + 1} \}$ .

What is the probability that $h(x_{n + 1})$ is the smallest in $h(S')$ , i.e., $\min h(S') = h(x_{n + 1})$ ? Conditioning on the minimum value of $\{ h(x_1), h(x_2), ..., h(x_n) \}$ ( $Z$ ) being some $z$ ( $z \in [0, 1]$ ), the probability becomes

\begin{aligned} \Pr \big[\min h(S') = h(x_{n + 1}) \mid Z = z \big] = \Pr \big[h(x_{n + 1}) \in [0, z] \mid Z = z \big] = z. \end{aligned}

Integrating over all possible values of $z$ , we have

\begin{aligned} \Pr[\min h(S') = h(x_{n + 1})] &= \int_{z = 0}^1 \Pr \big[\min h(S') = h(x_{n + 1}) \mid Z = z \big] \cdot p(z) \ dz \\ &= \int_{z = 0}^1 z \cdot p(z) \ dz \\ &= \mathbb{E} [Z] . \end{aligned}

But, by symmetry, $\Pr[\min h(S') = h(x_{n + 1})] = 1 / \big(N + 1\big)$ . Therefore, $\mathbb{E}[Z] = 1 / \big(N + 1\big)$ .

$\square$

Next we upper bound and lower the value of $Z$ .

Variance

As we need to bound the two side error of $Z$ , we can't use Markov inequality but rely on Chebyshev's inequality. In this section, we study the variance of $Z$ .

Theorem. $\mathbb{Var}[Z] \le 1 / \big(N + 1\big)^2$ .

Proof 1.

\begin{aligned} \mathbb{E} [ Z^2 ] &= \int_{z = 0}^1 N z^2(1 - z)^{N - 1} dz \\ &= \int_{z = 0}^1 N [(z - 1)^2 + 2(z - 1) + 1] (1 - z)^{N - 1}dz \\ &= -\frac{N}{N + 2}(1 - z)^{N + 2} \mid_{0}^1 + \frac{2N}{N + 1} (1 - z)^{N + 1} \mid_{0}^1 - \frac{N}{N} (1 - z)^{N} \mid_{0}^1 \\ &= \frac{N}{N + 2} - \frac{2N}{N + 1} + \frac{N}{N} \\ &= \frac{-(N - 1)(N + 2) + N^2 + N}{(N +2)(N + 1)} \\ &= \frac{2}{(N +2)(N + 1)} \end{aligned}

Hence, $\mathbb{Var} [ Z ] = 2 / \big( (N + 1)(N + 2) \big) - 1 / \big(N + 1\big)^2 \le 1 / \big(N + 1\big)^2$ .

$\square$

Proof 2.

\begin{aligned} \mathbb{E} [ Z^2 ] &= \int_{z = 0}^1 \Pr[ Z^2 \ge z ] \ dz \\ &= \int_{z = 0}^1 \Pr[ Z \ge \sqrt z ] \ dz \\ &= \int_{z = 0}^1 (1 - \sqrt z)^N \ dz \\ &\overset{t \doteq \sqrt z}{=} \int_{t = 0}^1 (1 - t)^N \ d t^2 \\ &= 2 \int_{t = 0}^1 (1 - t)^N (t - 1 + 1) \ d t \\ &= 2 \int_{t = 0}^1 (1 - t)^N - (1 - t)^{N + 1} \ d t \\ &= 2 \left( \frac{1}{N + 1} - \frac{1}{N + 2} \right) \end{aligned}

$\square$

Question to ponder: try to apply Chebyshev's inequality directly on this single estimate. Can we get a meaningful lower bound for $Z$ ?

Repetition

However, this alone is not enough to give an accurate estimate. Instead, we repeat the algorithm $k$ times, and take the average over the $Z$ 's.

Theorem. Let $Z_1, ..., Z_k$ be $k$ independent copies of $Z$ and define $\bar Z \doteq (1 / k) \sum_{i \in [k] } Z_i$ . Then $0 < \epsilon < 1$ ,
$\Pr \left[ \left| \bar Z - \frac{1}{N + 1} \right| \ge \frac{ \epsilon }{N + 1} \right] \le \frac{1}{k \cdot \epsilon^2}.$

Proof. By independence of $Z_i$ 's, we have

\mathbb{Var} [ \bar Z ] = \frac{1}{k^2} \cdot \sum_{i \in [k] } \mathbb{Var}[Z_i ] \le \frac{1}{k (N + 1)^2}.

The theorem follows directly from Chebyshev's inequality.

$\square$

That is, $\bar Z \in \big( 1 / (1 + N) \big) \big[ 1 - \epsilon, 1 + \epsilon \big]$ with probability $1 / \big( k \epsilon^2 \big)$ . It concludes that, with probability $1 / \big( k \epsilon^2 \big)$ ,

\frac{1}{ \bar Z } \in \left[ \frac{ N + 1 }{ 1 + \epsilon }, \frac{ N + 1 }{ 1 - \epsilon } \right].

Taking Quantiles

There exists other analysis for the concentration behavior when we repeat the experiment for $k$ times.

We need the following inequalities:

$\forall x \in \mathbb{R}$ , $1 + x \le e^x$ ;
$\forall x \in [0, 1]$ , $e^x \le 1 + 2x$ .

Now, for $N \ge 1$ ,

\begin{aligned} \Pr \left[ Z \ge \frac{1 + \epsilon}{N} \right] = \left(1 - \frac{1 + \epsilon}{N} \right)^N \le \exp \left( - \big( 1 + \epsilon \big) \right) = \frac{1}{e \cdot e^\epsilon}. \end{aligned}

\begin{aligned} \Pr \left[ Z \le \frac{1 - 2\epsilon}{N} \right] = 1 - \left( 1 - \frac{1 - 2\epsilon}{N} \right)^N \le 1 - \exp \left( - \big( 1 - \epsilon \big) \right) = 1 - \frac{e^\epsilon}{e}. \end{aligned}

We claim that if we take the $\frac{k}{\sqrt e}$ -th smallest element, with high probability,

\left| \overline X - \frac{1}{N + 1} \right| \le \epsilon \frac{1}{N + 1}.

Denote $z_1, z_2, ..., z_k$ a set of i.i.d Bernoulli variables with mean $\frac{1}{\sqrt e} e^{-\epsilon / 2}$ . Then by Chernoff bound,

\begin{aligned} \Pr[ \sum z_i \ge \frac{k}{\sqrt e} ] &= \Pr[ \sum z_i \ge (1 + (e^{\epsilon / 2} - 1) ) \frac{k}{\sqrt e} e^ {-\epsilon / 2}] \\ &\le \exp \left( -(e^{\epsilon / 2} - 1)^2 \frac{k}{\sqrt e} e^ {-\epsilon / 2} / 3 \right) \\ &= \exp \left( -(e ^\epsilon - 2 e^{\epsilon / 2} + 1) e^ {-\epsilon / 2} \frac{k}{\sqrt e} / 3 \right) \\ &= \exp \left( -( e^{\epsilon / 2} - 2 + e^ {-\epsilon / 2}) \frac{k}{\sqrt e} / 3 \right) \\ &\le \exp \left( - \frac{ \epsilon^2 }{4} \frac{k}{\sqrt e} / 3 \right) \\ & = \delta \end{aligned}

It suffices to set $k = \frac{12 \sqrt e}{\epsilon^2} \ln \frac{1}{\delta}$ .

By symmetry, we can prove the inequality of the other hand.

Remark 2: Suppose that we have a function $h$ that maps each of the $N$ elements to a non-negative real number according to exponential distribution $\exp(-1)$ independently (the same element is mapped to the same number), then the minimum of these real numbers serves also as an unbiased estimator of $\frac{1}{N}$ . To verify this,

\Pr[ Z \le z] = 1 - \exp(-zN)

Therefore,

p[Z = z] = \frac{\partial \Pr[ Z \le z]}{\partial z} = N \exp(-Nz).

and

\begin{aligned} \mathbb{E}[Z] &= \int_{0}^\infty Nz \exp(-Nz) dz \\ &= -\int_{0}^\infty z \ d\exp(-Nz) \\ &= -z \exp(-Nz) \mid_{0}^\infty + \int_0^\infty \exp(-Nz) dz \\ &= \frac{1}{N}. \end{aligned}

Further,

\begin{aligned} \Pr \left[ Z \ge (1 + \epsilon) \frac{1}{N} \right] &= \exp( - 1 - \epsilon) = \frac{1}{e}e^{-\epsilon}, \\ \Pr \left[ Z \le (1 - \epsilon) \frac{1}{N} \right] &= 1 - \exp( - 1 + \epsilon) = 1 - \frac{1}{e}e^{\epsilon}. \end{aligned}

Similarly, we can show that if we repeat the experiment $k = O(\frac{\ln 1 / \delta }{\epsilon^2 } )$ times, with probability at least $1 - \delta$ , the $\frac{1}{e}$ smallest elements is an $1 \pm \epsilon$ estimator of $\frac{1}{N}$ .

Solution 2

Suppose we only want to know whether $N \ge t$ or $N \le t / 2$ for a given integer $t$ , is this possible?

The answer is yes and the solution is amazingly easy. We hash each element in $\mathcal{U}$ uniformly at random into the range $[1, 2, 3, ..., t]$ . If $N \ge t$ , the probability that no elements is assigned the value $t$ is given by

(1 - 1 / t)^N \le (1 - 1 / t)^t \le 1/e

The second inequality holds since $(1 - 1 / t) \le e^{1 / t}$ .

On the other hand, when $N \le t / 2$ , the probability that no element is assigned the value $t$ is greater than

(1 - 1 / t)^N \ge (1 - 1 / t)^{t / 2} \ge 1 / e

The second inequality holds since $(1 - 1 / t) \ge e^{- 2 / t} = 1 - \frac{2}{t} + \frac{1}{2!}(\frac{2}{t})^2 - \frac{1}{3!}(\frac{2}{t})^3 + ...$ when $1 / t \le 1/ 2$ .

We can boost the probability to some defined threshold $1 - \delta$ by repeating $k = \log 1 / \delta$ times and check whether the majority of the answers are "yes". Note that the expected number of "yes" is more than $(1 - 1 / e)k$ and by chernoff bound the probability that less than $0.5 k$ "yes" are returned is given by $\delta$ .

Now, to estimate $N$ , we can set up $\log n$ values of $t: 1, 2, 4, 8, ..., n$ and test for each value of $t$ whether $N \ge t$ or $N \le t / 2$ . We can find an interval $[t_1, t_2]$ , such that $N \in [t_1, t_2]$ and $N / 2 \le t_1 \le t_2 \le 2\cdot N$ . The space complexity is $O(\log n \log 1 / \delta)$ .

Reference

[1] M. Charikar, T. Li, and A. Xue, “Lecture 1: Counting Distinct Elements,”, CS369G: Algorithmic Techniques for Big Data.