5
$\begingroup$

The width (number of registers) and depth (number of hash functions) of a Count-Min sketch determine the accuracy of counts retrieved.

I've found two different methods for calculating the width ($w$) and depth ($d$).

First Method

The clearest example I've found is from a 2011 paper by the original Count-Min authors:

Suppose we want an $\mathrm{error}$ of at most $0.1%$ (of the sum of all frequencies), with $99.9%$ $\mathrm{certainty}$. Then we want $2/w = 1/1000$, we set $w = 2000$, and $(1/2)^d = 0.001$, i.e. $d = \log 0.001/ \log 0.5 ≤ 10$.

From which I deduce that:

$w = \lceil 2/\mathrm{error}\rceil$

$d = \lceil \ln(1-\mathrm{certainty})/\ln(1/2) \rceil$

The description of Count-Min in Real-time Analytics (page 357) states:

In the original Count-Min paper, the authors show that the probability that the estimate of an element is between its true value $x$ and an upper bound $x + em$, where $m$ is the number of elements entered into a [Count-Min Sketch], is larger than $1-d$ under two conditions. The first condition is that the width of the sketch is $2/e$. The second condition is that the depth of the sketch is $(\log 1/d)/\log 2$. So, a Count-Min sketch where the estimate is within $5$ percent of the sum with a $99$ percent probability would have a width of $40$ and a depth of $7$. A depth of $8$ with a width of $128$ would have a relative error of approximately $1.5$ percent with a probability of approximately $99.6$ percent.

From which I deduce that (with $\mathrm{error}$ and $\mathrm{certainty}$ defined as above):

$w = \lceil 2/\mathrm{error} \rceil$

$d = \lceil \ln(1/(1-\mathrm{certainty}))/\ln(2) \rceil$

Which is equivalent to the first method, merely being a rearrangement of the logarithms.

And, for what it's worth, the implementation of Count-Min within stream-lib also uses an equivalent method:

$w = \lceil 2/\mathrm{error} \rceil$

$d = \lceil -\ln(1-\mathrm{certainty})/\ln(2) \rceil$

Second Method

Wikipedia, however, gives the following:

The parameters $w$ and $d$ can be chosen by setting $w = ⌈e/ε⌉$ and $d = ⌈\ln 1/δ⌉$, where the error in answering a query is within a factor of $ε$ with probability $δ$.

Which is seemingly extracted from a 2009 paper by one of the original Count-Min authors (Theorem 1, on page 2).

From this I deduce that (with $\mathrm{error}$ and $\mathrm{certainty}$ again defined as above):

$w = \lceil e/\mathrm{error} \rceil$

$d = \lceil \ln(1/(1-\mathrm{certainty})) \rceil$

This does not seem to be equivalent to the first method (and gives different results if I implement it).

Due to the volume of evidence I'm guessing that the first method is the correct one, but is it? Are there subtle differences between them that I'm not understanding?

$\endgroup$
  • $\begingroup$ Have you tried reading the paper, finding the method it gives for bounding the error and certainty, computing the parameters each formula gives for a particular example, and then bounding the error and certainty for each using the paper's method, to see what you get? It's possible that all of the formulas are correct, but lead to slightly different widths/depths and space/time tradeoffs. $\endgroup$ – D.W. Jul 28 '15 at 16:53
  • 1
    $\begingroup$ It seems that they converted from natural logarithm to $\log_2$: $e$ has changed into 2, and $\ln(x)$ has changed into $ln(x)/\ln(2)$. Without reading, it is either a small mistake in the 2009 version, or a minor (presentation) improvement in the 2011 paper. $\endgroup$ – Ran G. Jul 28 '15 at 17:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.