Count Min Sketch: How to handle counters overflow?

Question

So the whole point of Count-Min Sketch is to update certain counters depending on the results of the provided hash functions. But, these counters are limited in memory, and after running for quite some time, they might overflow, dropping from the MAX value to the MIN value (like Integers do). Assuming all I need is the N most frequent values in the sketch, is there a way to avoid this other than restarting the sketch every once in a while?

Answer 1

Use an appropriately sized integer if this worries you.

An 8-byte (long long) unsigned integer has a maximum value of 18,446,744,073,709,551,615. That should probably be enough.

Edit

Assuming all I need is the N most frequent values in the sketch, is there a way to avoid this other than restarting the sketch every once in a while?

Perhaps you could adapt reservoir sampling to your needs.