Before revision: We study sketching schemes for the cardinality estimation problem in data streams, and advocate for measuring the efficiency of such a scheme in terms of its MVP: Memory-Variance Product, i. e., the product of its space, in bits , and the relative variance of its estimates. Under this natural metric, the celebrated HyperLogLog sketch of Flajolet et al. (2007 ) has an MVP approaching 6(3\ln 2-1)\approx 6.48 for estimating cardinalities up to 2^{64.
After revision: We study sketching schemes for the cardinality estimation problem in data streams, and advocate for measuring the efficiency of such a scheme in terms of their memory-variance product (MVP). E.g., a sketch that occupies 5m bits and whose relative variance is 2/m (standard error \sqrt{2/m ) has an MVP approaching 6(3\ln 2-1)\approx 6.48 for estimating cardinalities up to 2^{64.