I've been reading about count-min sketch and I'm interested in the performance of this data structure when doing conservative updates. To my understanding from the Wikipedia article, conservative updating means that when you see an item, instead of incrementing all the counters you only increment the counter(s) that have the lowest current count. Intuitively, I understand that this method will give a strictly better estimate than the standard update procedure because collisions are now less likely to cause us to overestimate a count.

I know that it's possible with traditional count-min sketch to tune the parameters of the data structure based on the error rate $\delta$ you're willing to tolerate. This error analysis shows that to solve $\epsilon$-approximate heavy hitters with probability $1 - \delta$, we should use a sketch with $\frac{e}{\epsilon}$ columns and $\ge \ln \frac{1}{\delta}$ rows/hash functions. What would this analysis look like if we were performing conservative updates?

I found this paper which I believe calculates the probability of a false negative using conservative updates to be $(1 - (1-\frac{1}{W})^N)^d$ where $W=\frac{e}{\epsilon}$ is the number of columns, $N$ is the number of unique additions, and $d$ is the number of rows. What I don't understand:

  • How does this calculation take into account the fact that only the counter(s) with lowest current count are incremented in each step?
  • Intuitively, why does this probability depend on the size of the stream $N$ (where it seems that the probability of false negatives in traditional count-min sketch does not?)

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.