Frequency Counting Algorithms Over Data Streams

Re:Frequency Counting Algorithms Over Data Streams by talaketu on Monday July 20, 2015 @10:17PM (#9920230)

> “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.

[ Parent | on HN ]

Re:Frequency Counting Algorithms Over Data Streams by haberman on Monday July 20, 2015 @11:09PM (#9920370)

> 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.

[ Parent | on HN ]

Re:Frequency Counting Algorithms Over Data Streams by ted_dunning on Tuesday July 21, 2015 @04:07AM (#9921002)

Count-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.

[ Parent | on HN ]