count-min

Definition

The counting scheme behind the Count-Min sketch: increment a counter in each of several independently hashed rows, then answer a query with the minimum across those rows. Collisions can only inflate a counter, never deflate it, so the estimate is one-sided — never below the true count, and above it only by a bounded amount with high probability. Taking the min is what strips out most of the collision noise.