0
$\begingroup$

I read almost everything I can find for count min sketch. Also look at most of the videos in Youtube, but did not found answer of a simple question -

What is the proper way to calculate dimensions of count min sketch

In both ChatGPT and Bing AI, if you ask how big a count min sketch needs to be in order to be able to "hold" counts for 1M elements with error 1%, bot gives you something small like:

Bing: 272 columns and 5 rows ChatGPT: 200 columns and 40,000 (!!!) rows

40,000 rows is definitely overkill, but I columns has to be more as well.

If we hash 1M different items in 272, 200 or even 40K "pigeon holes" we will have more than one "pigeon" in each hole. In fact holes will be very crowded and pigeons won't able to live.

If I check the bloom filter calculator here, https://hur.st/bloomfilter/?n=1000000&p=0.01&m=&k=

if I have 1 hash function, optimal width is 100x the items (99,499,163) and optimal solution is with 7 hash functions and 10x width (9,585,059).

I can imagine I can store 1'000 items in 1'000 slots (note no hash function can do that), but 200 columns sounds ridiculous.

What I am missing?

$\endgroup$

1 Answer 1

2
$\begingroup$

In order to correctly compute the sketch dimensions, you need first to decide the error $\epsilon$ and the probability of failure $\delta$. This is because Count-min sketch, denoting with $\boldsymbol{s}$ the vector corresponding to the stream of items, and with $w$ and $d$ respectively the number of buckets (columns) and rows, provides the following guarantees:

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\|\boldsymbol{s}\|_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.

In your case, you fixed $\epsilon = 0.01$ (i.e., $1\%$). Fixing $\delta = 0.04$ the guarantees hold with probability at least $1 - 0.04 = 0.96$. The corresponding dimensions are $w=\left\lceil\frac{e}{\varepsilon}\right\rceil = 272$ and $d=\left\lceil\ln \frac{1}{\delta}\right\rceil = 4$.

Fixing $\delta = 0.01$ (for a stronger guarantee holding with probability at least $1-0.01=0.99$) you get $d=\left\lceil\ln \frac{1}{\delta}\right\rceil = 5$.

$\endgroup$
8
  • $\begingroup$ OK, I read this like 20 times from different sources, but then, if I insert 1000 unique items, every single row, which is kind of hash-table will be fully saturated (3-4 items in every cell). Then any key, no matterm if it was inserted or not will report 1000 / 272 = 3.6 count on average, which definitely break the things. Sure heavy hitter will have more than 3.6 hits. Is that the "hidden" purpose of the sketch? If we calc for 1M items it will go to 3676.47 average count. then we will still be able to recognize the heavy hitter, but real count will be really far from the truth. $\endgroup$
    – Nick
    Mar 6 at 8:13
  • $\begingroup$ Am I do not understanding the purpose of count min sketch? I thought the purpose is to keep the count of the elements $\endgroup$
    – Nick
    Mar 6 at 8:15
  • $\begingroup$ Yes, definitely you are missing the key points. First, Count-min sketch is meant for frequency estimation, not for detection of heavy hitters (it can be adapted for this task, but there are better algorithms); second, the sketch is meant to provide the additive guarantee that I reported with high probability; third, and this may be counterintuitive for you, collisions are an opportunity, not an issue: they are exploited to guarantee high-quality estimates. $\endgroup$ Mar 6 at 13:39
  • $\begingroup$ You are probably confused by the fact that the reported estimates are approximate, not exact values (counts can not be exact unless using one counter for each item belonging to the universe set from which stream items are drawn; but this in turn requires a lot of space, and the purpose of the sketch is to provide a trade-off between the space actually used and the quality of the approximation guaranteed). $\endgroup$ Mar 6 at 13:43
  • $\begingroup$ So the only guarantee is, if we have three items and one have high count, other two have small count which is similar, it means that the real count of first value is higher than the other two. Is that correct ? $\endgroup$
    – Nick
    Mar 6 at 13:46

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.