twitter/algebird — pull request #74 by echen (2012-12-16 22:17:02+00:00)
Title: Add heavy hitters to Count-Min sketch.

I added a method to pull out all heavy hitters (items that appear at least `heavyHittersPct * totalCount` times in the stream). It returns all true heavy hitters, but may (with low probability) return some false ones as well.

Notes:
- `cms.heavyHitters` currently returns a `Set[Long]`, but since this set is "approximate", it could become another instance of the `ApproximateSet` stuff in #44.
- The set of heavy hitters and their estimated counts is backed by a `SortedSet`. I wanted a min-heap, but it doesn't look like the standard Scala collections has an immutable one (though there is a *mutable* `PriorityQueue`).
- The set of input parameters for each CMS structure was becoming unwieldy (I had to add a new `heavyHittersPct` parameter for the heavy hitter threshold), and I guess there may be others as we add new estimation methods, so I moved these inside a simple `CMSParams` container.