Follow up this question:

What is the correct way to determine the width and depth of a count-min sketch?

Let suppose, correct way is following:

w = ceil(2 / error)
d = ceil(−ln(1−certainty)/ln(2))

If we choose

error     = 0.01
certainty = 0.95

Result will be 200 x 4 = 800 counters, if 4 bytes per counter - bit more than 3 KB.

My question is following - if we put 800'000 or even 200'000 different elements, the sketch will be saturated and counters will show unrealistic data.

How we can calculate or estimate this saturation of the counter, so we "allocate" bigger array that will not be saturated?



Your Answer

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