addthis/stream-lib — pull request #57 by zollman (2014-01-02 13:52:28+00:00)
Title: Fix StreamSummary when incrementCount > 1

There appears to be a bug in how incrementCounter (
https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/StreamSummary.java#L154 ) is implemented for counts > 1.

The top-k Space-Saving paper at https://icmi.cs.ucsb.edu/research/tech_reports/reports/2005-23.pdf assumes that whenever an item is seen, you’re only ever incrementing the count by 1. Given the way they create and merge buckets, the list of counts is always in descending order (the counts may be off by a large error, but the buckets are always ordered using the item count, ignoring whatever the error is set to.)

This implementation of incrementCounter() allows you to increment by more than one, but it allows our list of stream counts to get out of order: if I have counts A:8,B:6,C:5 in the stream, and I add D:10, the Space-Saving algorithm suggests it should bubble to the top: D:10,A:8,B:6,C:5.
But in this case it doesn’t: I get A:8,B:6,C:5,D:10.

Since every add only checks to see if the bucket above it is equal to the new count for the item being added (line ref aboved), any new item added with either replace the D:10 bucket or be added below it, unless you add an item after it with count < 10 and then increment() enough to bring the count up to 10. Since the algorithm drops the last bucket in the list (calls it “min”, even though in this case it’s not), you get stuck dropping and replacing the last item all the time.

Meanwhile, the peek function the top-K items, assumes the buckets are in order:
https://github.com/addthis/stream-lib/blob/master/src/main/java/com/clearspring/analytics/stream/StreamSummary.java#L196