addthis/stream-lib — pull request #72 by mspiegel (2014-05-02 19:54:57+00:00)
Title: Bugfixes to CountMinSketchTest.

In response to https://github.com/addthis/stream-lib/issues/59

This fixes the CountMinSketch string key test. Previously the test
was attempting to mimic the behavior of the integer key test. The
set of a Strings of size |N| is much larger then the set of all
integers from 0 to N so a different strategy is necessary. Generate
some strings to insert into the sketch and then generate some test
strings that are likely not in the sketch.

Bugfix for the tolerance calculations. The guarantee is that
(estimate <= actual + epison * cardinality) with some probability,
or rewriting the terms (estimate - actual) / cardinality <= epsilon.