CountMin sketch, part 2: proving error bound

We frame and then prove the bound that says the count estimate produced by a CountMin point query is "probably not too far" from the correct count. The proof uses universality, Markov's inequality, and linearity of expectation, among other ideas. Finally, we consider how large the sketch must be to achieve particular bounds.

These materials are also openly available on figshare. Please cite this work; this ensures that funding agencies see the impact and importance of these open learning materials.

Channel: @BenLangmead

[the_Spartan_]

Just wanted to say, your explanation was top-notch! I gained a lot from it and really appreciate the effort you put in. Thanks a bunch!

[nmmm]

one of the best lection about CMS. However one question remains... how to calculate W and D if we know the element we will put inside the sketch (or total element of the stream)