twitter/algebird — pull request #46 by echen (2012-12-06 09:13:44+00:00)
Title: Add inner product estimation to Count-Min sketch.

This is in response to the email Avi sent about using Count-Min sketch to estimate the total join size between two pipes. (which could be used to set the number of reducers when performing a join)

1. So the main change is, obviously, adding inner product estimation to the Count-Min sketch structure.

2. Previously, my confidence and error bounds were described in terms of (depth = # of hash functions, width = range of hash values), but I switched these to the eps and delta parameters that most papers seem to use instead. (e.g., "with probability 1 - delta, the estimate is within a multiplicative epsilon factor of the true...") In retrospect, I think I should have defined the CMS structures to take (eps, delta) as constructor parameters, instead of (depth, width). We could always add them as another constructor. Thoughts?

3. Other minor refactorings.