0
$\begingroup$

Most of the sources about count min sketch say it usage is to give counts for several "items" stored "inside".

However in the following this question
What is the proper way to calculate dimensions of count min sketch
I made valid point if count min sketch is very saturated, it will always return wrong overestimated count, no matter what "item" it is queried about.

This is when the "items" are much more than the columns of the count min sketch, for example let suppose we have 272 columns and 1'000 items. Then no matter of the hash function, all counters will be equal to 1000 / 272 = 3.

Only exception will be frequent items (heavy hitters) which will have count bigger than 3.

What are the guarantees of the result?

  • Obviously more frequent items will have higher count.
  • Count seems to be proportional to the item frequency?
  • anything else?

What count min sketch is good for?

  • Obviously it is NOT good for keeping count of items.
  • If is paired with heap - detecting heavy hitters / abnormalities? - I can see similarities with Misra - Gries algorithm, since it also can not give exact count, but paired with heap detects heavy hitters very well.
  • anything else?
$\endgroup$

1 Answer 1

1
$\begingroup$

You stated "Obviously it is NOT good for keeping count of items".

The sentence shows that you lack a clear understanding of both the problem that the Count-min sketch tries to solve (in particular how much difficult it is) and of the techniques it actually uses.

Let's start with the problem. Count-min is a frequency estimator. Why an estimator? Why not use exact counts? Let $\mathcal{U}$ be the universe set from which the items belonging to a stream $\sigma$ are drawn, and let $m$ be the cardinality of $\mathcal{U}$. The stream $\sigma$ may be even a continuous and unbounded sequence of items. Without loss of generality, we a priori set its length $n$ for convenience. In order to store exact counts you need $\Omega(m)$ space, i.e. space linear in the cardinality of the universe set. But, $m$ may be arbitrarily high so that in many situations exact counts are simply ruled out: at least, exact count are not practical.

This is why we use frequency estimators: we can't afford to use linear space, and frequency estimators can work with sub-linear space. This is the first key point you need to understand: if we use less than linear space, we must forget solving exactly the frequency estimation problem.

So, we have to settle for an approximate solution. Let $[x] = \{1,2,\cdots,x\}$. The frequency of an item is defined as follows.

Given a stream $\sigma$ of $n$ elements, the frequency of an item $s\in \mathcal{U}$ is the number of occurrences of $s$ in $\sigma$, that is $f_\sigma(s) = \left\vert\{i\in [n]: s_i = s\}\right\vert$.

A stream $\sigma$, whose items are drawn from the universe $[m]$, implicitly defines a frequency vector, $\mathbf{f}=(f_1, f_2, \ldots, f_m)$, where $f_i=f_\sigma(i)$ is the frequency of item $i$. We can interpret $\sigma$ as a sequence of updates to $\mathbf{f}$: initially $\mathbf{f}$ is the null vector, then, for each item in the stream, the entry in $\mathbf{f}$ corresponding to the frequency of that item is incremented by one.

$\epsilon$-approximate frequency estimation problem:

Given a stream $\sigma$ of $n$ elements drawn from the universe $[m]$, the frequency vector $\mathbf{f}$ defined by $\sigma$, and a value ${0<\epsilon<1}$, the $\epsilon$-approximate frequency estimation problem consists in computing a vector $\mathbf{\hat{f}}=(\hat{f}_1, \hat{f}_2, \ldots, \hat{f}_m)$, so that $\left\vert\hat{f}_i-f_i\right\vert \le \epsilon \lVert\mathbf{f}\rVert_\ell$, for each $i\in[m]$ where $\ell$ can be either 1 or 2.

The quality of the output provided by a randomized algorithm (Count-min is a randomized algorithm) depends on the error committed estimating the quantity of interest. This is the second key point that you need to truly understand: we are interested only to randomized algorithms that may be wrong, but only with some small and controlled probability. In particular, we may require either an additive or a multiplicative approximation. Here, we define only what an additive approximation means, since Count-min relies on this type of approximation.

Let $A(\sigma)$ denote the output of a randomized streaming algorithm $A$ on input $\sigma$; it is worth noting here that $A(\sigma)$ is a random variable. Moreover, let $f(\sigma)$ be the function that $A$ is supposed to compute. The algorithm $A$ ($\epsilon$, $\delta$) additively approximates $f$ if $\Pr[|A(\sigma) - f(\sigma)| > \epsilon] \leq \delta$. Here ${0<\epsilon<1}$ is an accuracy parameter, and ${0<\delta<1}$ is a probability of failure (our confidence in the result).

Let $w$ and $d$ be respectively the number of buckets (columns) and rows of the sketch. Count-min provides the following guarantees for an estimate $\hat{a}_i$ of the item $a_i$:

if $w=\left\lceil\frac{e}{\varepsilon}\right\rceil$ and $d=\left\lceil\ln \frac{1}{\delta}\right\rceil$, an estimate $\hat{a}_i$ is such that $a_i \leq \hat{a}_i$ and $\hat{a}_i \leq a_i+\varepsilon\|\mathbf{f}\|_1$ with probability at least 1 - $\delta$.

Note that the length of the stream is not relevant, and, indeed, the sketch dimensions are independent from the length of the stream.

The sketch provides this remarkably good additive approximation through a clever combination of the following techniques:

  • it is designed to be extremely close (with regard to the previous additive bound) to exact on expectation (proved by using a sum of indicator variables and the linearity property of the expectation);

  • how much does it drift from the expectation? Provably, not enough to provide bad estimates (again, with regard to the additive bound): a concentration of measure inequality (Markov inequality) can be used to prove this fact;

  • the probability of getting good estimates is amplified by a well known trick for a randomized algorithm, i.e. the use of multiple repetitions of experiments: in the sketch case, you can think of one row as an experiment, the sketch is aptly sized so that the number of rows provides the required probability;

  • it uses pairwise independent hash functions, which, informally stated, means that any pair of items is unlikely to collide. Of course, collisions happen for largely sized streams, but they are exploited by the algorithm, not suffered (you must be truly unlucky for collisions to be able to make the probabilistic bound invalid).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.