  Count-Min sketch is a hash-based data structure to represent a dynamically
changing associative array of counters. Here we analyse the counting version of
Count-Min under a stronger update rule known as \textit{conservative update},
assuming the uniform distribution of input keys. We show that the accuracy of
conservative update strategy undergoes a phase transition, depending on the
number of distinct keys in the input as a fraction of the size of the Count-Min
array. We prove that below the threshold, the relative error is asymptotically
$o(1)$ (as opposed to the regular Count-Min strategy), whereas above the
threshold, the relative error is $\Theta(1)$. The threshold corresponds to the
peelability threshold of random $k$-uniform hypergraphs. We demonstrate that
even for small number of keys, peelability of the underlying hypergraph is a
crucial property to ensure the $o(1)$ error. Finally, we provide an
experimental evidence that the phase transition does not extend to non-uniform
distributions, in particular to the popular Zipf's distribution.
