3 ms·
> “Which pages are getting an unusual hit in the last 30 minutes?” A good statistic for this is an exponentially weighted moving average, which can be computed
by talaketu 11y ago
> “Which pages are getting an unusual hit in the last 30 minutes?”
A good statistic for this is an exponentially weighted moving average, which can be computed online by a leaky integrator using a single accumulator register per counted entity.
It's not so much as counting, as estimating a rate.
- haberman 11y ago> a single accumulator register per counted entity. That requires O(n) memory space, where n is the number of counted entities. If you're willing to spend this much memory, the problem is easy. Algorithms like the one in the article (or the paper I mentioned) are for when you want to use far less memory than that.
- ted_dunning 11y agoCount-min sketches can be adapted to use exponential decay. Presumably any sort of recurrent decay could be used to get approximately rectangular windows as well.