Problem

We study the problem of estimating the number of distinct elements in a stream SS. WLOG, we assume that elements in SS come from a domain [d]={1,2,...,d}[d] = \{1, 2,..., d \}, and that each element in [d][d] appears in the SS at least once. Hence, the problem is equivalent to the one of estimating dd.

k Minimum Values

The algorithm of kk-minimum values returns a (1±ϵ)(1 \pm \epsilon) estimate d^\hat d of dd, with probability at least 1−δ1 - \delta.

The algorithm picks a pairwise independent hash function g:[d]→[m]g : [d] \rightarrow [m] and uses a min heap hh that keeps the kk minimum hash values. When it stops, it outputs an estimate

d^≐k⋅m/v, \hat d \doteq k \cdot m / v,

where vv is the maximum element in hh. Observe that vv is also the kk-th minimum hash value of the set

{g(1),g(2),...,g(d)}. \{ g(1), g(2), ..., g(d) \}.

Algorithm: kk-minimum values.

  1. Select a pair-wise independent hash function g:[d]→[m]g: [d] \rightarrow [m], where m≥d2/δm \ge d^2 / \delta;
  2. Initialize a set h←{}h \leftarrow \{ \};
  3. For s∈Ss \in S do:
  4. \qquad If g(s)∈hg(s) \in h then continue;
  5. \qquad h←h∪{g(s)}h \leftarrow h \cup \{ g(s) \};
  6. \qquad If ∣h∣>k|h| > k then
  7. \qquad \qquad remove the max element in hh;
  8. Let v←v \leftarrow max element in hh.
  9. Return d^≐k⋅m/v\hat d \doteq k \cdot m / v.

Theorem 1.

With probability at least 1−δ1 - \delta, there isn't hash collision.

Proof:

For i≠j∈[d]i \neq j \in [d], as gg is pair-wise independent, Pr⁡[g(i)=g(j)]=1m\Pr[ g(i) = g(j) ] = \frac{1}{m}. Therefore,

E[∑i≠j∈[d]1[g(i)=g(j)]]=∑i≠j∈[d]E[1[g(i)=g(j)]]≤d2m=δ, \mathbb{E} \left[ \sum_{i \neq j \in [d]} \mathbf{1} \big[ g(i) = g(j) \big] \right] = \sum_{i \neq j \in [d] } \mathbb{E} \left[ \mathbf{1} \big[ g(i) = g(j) \big] \right] \le \frac{d^2}{m} = \delta,

where 1[g(i)=g(j)]\mathbf{1} \big[ g(i) = g(j) \big] is the indicator random variable of g(i)=g(j)g(i) = g(j).

By Markov's inequality,

Pr⁡[∑i≠j∈[d]1[g(i)=g(j)]≥1]≤δ. \Pr \left[ \sum_{ i \neq j \in [d] } \mathbf{1} \big[ g(i) = g(j) \big] \ge 1 \right] \le \delta.

□\square

Theorem 2.

With probability at least 1/(kϵ2)1 / (k\epsilon^2),

d^<d1−ϵ. \hat d < \frac{d}{1 - \epsilon}.

Proof: For i∈[d]i \in [d], define the indicator random variable of Xi=I[g(i)≤(1−ϵ)⋅k/d⋅m]X_i = \mathbb{I}\big[ g(i) \le (1 - \epsilon) \cdot k / d \cdot m \big]. Recall that

v≐The k-th smallest element of {g(1),g(2),...,g(d)}. v \doteq \text{The } k\text{-th smallest element of } \{ g(1), g(2), ..., g(d) \}.

The event that

{v≤(1−ϵ)⋅k/d⋅m}≡{d1−ϵ≤k⋅mv} \left\{ v \le (1 - \epsilon) \cdot k / d \cdot m \right\} \equiv \left\{ \frac{d}{1 - \epsilon} \le \frac{ k \cdot m }{ v } \right\}

happens if only ∑i∈[d]Xi≥k\sum_{i \in [d] } X_i \ge k.

By definition of XiX_i,

p≐Pr⁡[Xi]=(1−ϵ)⋅kd. p \doteq \Pr \left[ X_i \right] = (1 - \epsilon) \cdot \frac{ k }{d}.

By linearity of expectation, we have

E[∑i∈[d]Xi]=d⋅p=(1−ϵ)⋅k. \mathbb{E} \left[ \sum_{i \in [d] } X_i \right] = d \cdot p = (1 - \epsilon) \cdot k.

As gg is pair-wise independent, so are the XiX_i's. It follows that

σ2=Var[∑i∈[d]Xi]<d⋅p=(1−ϵ)⋅k. \begin{aligned} \sigma^2 =\mathbb{Var} \left[ \sum_{i \in [d] } X_i \right] < d \cdot p = (1 - \epsilon) \cdot k. \end{aligned}

By monotonicity of probability and by Chebyshev's inequality,

Pr⁡[∑i∈[d]Xi≥k]≤Pr⁡[∣∑i∈[d]Xi−(1−ϵ)⋅k∣≥ϵk]<(1−ϵ)⋅kϵ2k2<1ϵ2k. \begin{aligned} \Pr\left[ \sum_{i \in [d] } X_i \ge k \right] &\le \Pr\left[ \left| \sum_{i \in [d] } X_i - (1 - \epsilon) \cdot k \right| \ge \epsilon k \right] < \frac{ (1- \epsilon) \cdot k }{ \epsilon^2 k^2 } < \frac{1}{\epsilon^2 k}. \end{aligned}

□\square

Theorem 3.

With probability at least (1+ϵ)/(kϵ2)(1 + \epsilon) / (k\epsilon^2),

d^≥d1+ϵ. \hat d \ge \frac{d}{1 + \epsilon}.

Proof: For i∈[d]i \in [d], define the indicator random variable of Yi=I[g(i)≤(1+ϵ)⋅k/d⋅m]Y_i = \mathbb{I}\left[ g(i) \le (1 + \epsilon) \cdot k / d \cdot m \right]. Recall that

v≐The k-th smallest element of {g(1),g(2),...,g(d)}. v \doteq \text{The } k\text{-th smallest element of } \{ g(1), g(2), ..., g(d) \}.

The event that

{v > (1+ϵ)⋅k/d⋅m}≡{d1+ϵ>k⋅mv}≡{d1+ϵ>d^} \left\{ v \ > \ (1 + \epsilon) \cdot k / d \cdot m \right\} \equiv \left\{ \frac{d}{1 + \epsilon} > \frac{ k \cdot m }{ v } \right\} \equiv \left\{ \frac{d}{1 + \epsilon} > \hat d \right\}

happens if only ∑i∈[d]Yi<k\sum_{i \in [d] } Y_i < k.

By definition of YiY_i,

q≐Pr⁡[Yi]=(1+ϵ)⋅kd. q \doteq \Pr \left[ Y_i \right] = (1 + \epsilon) \cdot \frac{ k }{d}.

By linearity of expectation, we have

E[∑i∈[d]Yi]=d⋅q=(1+ϵ)⋅k. \mathbb{E} \left[ \sum_{i \in [d] } Y_i \right] = d \cdot q = (1 + \epsilon) \cdot k.

As gg is pair-wise independent, so are the XiX_i's. It follows that

σ2=Var[∑i∈[d]Yi]=∑i∈[d]Var[Yi]=d⋅q⋅(1−q)=(1+ϵ)⋅k⋅(1−q). \begin{aligned} \sigma^2 =\mathbb{Var} \left[ \sum_{i \in [d] } Y_i \right] &= \sum_{i \in [d] } \mathbb{Var} \left[ Y_i \right] \\ &= d \cdot q \cdot ( 1 - q) \\ &= (1 + \epsilon) \cdot k \cdot (1 - q). \end{aligned}

By monotonicity of probability and by Chebyshev's inequality,

Pr⁡[∑i∈[d]Yi<k]≤Pr⁡[∣∑i∈[d]Yi−(1+ϵ)⋅k∣≥ϵk⋅1−q]≤(1+ϵ)⋅kϵ2k2≤1ϵ2k. \begin{aligned} \Pr\left[ \sum_{i \in [d] } Y_i < k \right] &\le \Pr\left[ \left| \sum_{i \in [d] } Y_i - (1 + \epsilon) \cdot k \right| \ge \epsilon k \cdot \sqrt{ 1 - q } \right] \\ &\le \frac{ (1 + \epsilon) \cdot k }{ \epsilon^2 k^2 } \\ &\le \frac{1}{\epsilon^2 k}. \end{aligned}

□\square

Reference

[1] G. Cormode and K. Yi, Small Summaries for Big Data, 1st ed. Cambridge University Press, 2020.