News for hackers. Stuff that matters.

A comment on Frequency Counting Algorithms Over Data Streams. Parent comment

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 ]