Frequency Estimators

Problem

A stream $S$ (viewed as a multi-set) of $n$ elements each from a domain $U = [1, , 2, ..., u]$. Estimate the number of times each element appears in the $S$.

If we use a balanced binary search, this can be done in $O(n \log \min\{n, u\})$ time and $\Theta(\min\{n, u\})$ space. If we use a hash table, this can be done in $\Theta(\min\{n, u\})$ time and space.

Question to ponder: can we do it with sub-linear space?

By allowing errors, this is possible. Let $a = \left< a_1, a_2, ..., a_{u} \right>$ be the frequency of elements in $U$ and $b = \left< b_1, ..., b_{u} \right>$ be our estimation. Our goal is to minimize the $\ell_\infty$ error:

Count-Min Sketch

We use array $A$ with size $m < \min\{n, u\}$ such that each element in $U$ is allocated a bucket in $A$ to keep its frequency. Some elements must share the buckets. Now we apply the following strategy:

1. Pick a perfect hash function $h : U \rightarrow [m]$ (this condition can be weaken, but for convenience of discussion, we assume perfectness here), that maps the elements uniformly to every bucket in the array.
2. For $\forall s \in S$,
   $\qquad A[h(s)] \leftarrow A[h(s)] + 1$ .
3. Return $b_i = A[h(i)]$ as the estimation of $a_i$.

Intuitively, each slot obtains $\frac{1}{m}$ fraction of the total mass $\sum_i a_i = |a|$ (where $|\cdot |$ denotes the $\ell_1$ norm). Conditioned on $i$-th element is hashed to the $h(i)$ slots, $\frac{1}{m}$ fraction of the rest mass $\sum_{j \neq i} a_j = n - a_i$ is hashed to the $h(i)$-th slot. Therefore, in expectation,

An interesting property is that, if some $a_j$ ($j \neq i$) (or a small subset of $a_j$'s) constitutes, say $0.99$ percent of the mass $|a|$, as long as it is not hashed to $h(i)$, then the expected error is less than $0.01 \frac{|a|}{m}$.

Formally, define the binary random variables $X_j$ for $j \neq i$ such that

Then by perfectness of $h$, $\Pr[X_j = a_j] = \frac{1}{m}$ and $\mathbb{E}[X_j] = \frac{a_j}{m}$. (Indeed, pairwise independence of $h$ suffices to guarantee this condition).

Then

As $b_i - a_i$ is non-negative, by Markov inequality,

If we would like to achieve failure probability $\delta$, we can set $m = \epsilon^{-1} \delta^{-1}$.

Question to ponder: can we improve this?

Yes, by repetition. Instead of using just one array, we set $d$ arrays (to be set latter) and choose $d$ hash functions independently. Then the probability that all estimations deviate more than $\epsilon |a|$ is at most

When $d = \ln{\delta} / \ln \frac{1}{\epsilon m} = \ln{ \frac{1}{\delta} } / \ln \epsilon m$, the failure probability decreases to $\delta$. To minimize the space usage, we solve the following optimization problem:

Solving the equation gives $m = e \epsilon^{-1}$. The space consumption is $\frac{e}{\epsilon} \ln \frac{1}{\delta}$.

Note: suppose that $|a| = 10000$ and $\epsilon = 0.1$, $\delta = 0.01$, then with $10 \cdot e \ln 100 \approx 125$ words, we can estimate a particular $a_i$ with the absolute error less than $1000$. If $a_i = 9000$, the relative error is small. However, if $a_i = 1$, basically our estimation if rather inaccurate.

Question to ponder: what if we analyze this by Chernoff style inequality?

If we make $d$ repetition, then the confidence interval of the mean estimation is given by (Hoeffding's inequality)

If we want this interval to be smaller than $\epsilon |a|$, then we need $d = \frac{ \log \frac{2}{\delta} }{2 \epsilon^2}$, which is a $\frac{1}{\epsilon }$ worse than the above analysis. Intuitively, we require stronger condition for concentration of mean value than that for existence of near-min value.

Count-Sketch

One drawback of Count-Min Sketch is that the estimator constructed is one-sided and not unbiased. This can be fixed by introducing an additional function $g : U \rightarrow \{ - 1, 1 \}$ that gives each elements in $U$ a sign ("+" or "-") independently and uniformly at random. Now,

2. For each element $s \in S$, we increase the counter $h(s)$ in the array by 1 if $g(s) > 0$ or $-1$ if $g(s) < 0$.
3. Finally, we set $b_i = A[h(i)] \cdot g(i)$ as the estimation of $a_i$.

In expectation, each slot obtains $\frac{1}{m}$ fraction of the total mass $\sum_i a_i = |a|$. But as each element "flips" it sign randomly, the expected value obtained is 0. Now, conditioned on $i$-th element is hashed to the $h(i)$ slots, $\frac{1}{m}$ fraction of the rest mass $\sum_{j \neq i} a_j = n - a_i$ is hashed to the $h(i)$-th slot. With their signs flipped randomly, they contribute 0 to the $h(i)$-th slot. Hence,

Formally, define the binary random variables $X_j$ for $j \neq i$ such that

Then by perfectness and independence of $h$ and $g$,

and

where $|a|_2^2$ is the $l_2$ norm of $a$. Note that the above analysis requires only pair independence. The random variable $X_j$ is two sided, therefore we can not use Markov Inequality for analysis.

Question to ponder: is it possible to analyze this directly by Chernoff style inequality?

The tool we resort to is Chebyshev's inequality:

we take $m = k\epsilon^{-2}$ for some integer $k> 2$.

How do we amplify the successful probability? We repeat the experiment $d$ times, and take the median. The only way that the median makes a mistake is when more than half of the estimations deviate more $\epsilon |a|_2$. Denote $Y$ the number of estimation such that the error is more than $\epsilon |a|_2$. By Chernoff,

which solves to

The overall space usage is therefore

Question to ponder: the expression is wired, which implies that $k \rightarrow \infty$, the space usage converges to $\frac{12}{\epsilon^2} \log \frac{1}{\delta}$, which is worse than count-min hash than a $\frac{1}{\epsilon}$ factor.

Relation between $|a|_1$ and $|a|_2$.

Their relation is given as follows (by concavity of the $\sqrt \cdot$ function)

In particular, when $|u| = 2$, the inequality becomes

When the dimension is higher than $2$, the factor in the RHS can not bounded to $\sqrt 2$.