A d × w grid of counters with d hash functions. Update: add 1 to one cell per row. Query: take the minimum across rows. Estimate is an overcount, never an undercount.
| Operation | Cost |
|---|---|
| Update (add 1 per row) | O(d) |
| Query (min across rows) | O(d) |
| Merge (add two grids) | O(d·w) |
| Space (the grid) | O(d·w) |
| Error (overcount) | ≤ eps·N |
| Width w | ceil(e/eps) |
| Depth d | ceil(ln(1/δ)) |
| Guarantee | f ≤ est, never below |