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.
After revision: Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA are mergeable, which means that large data sets can be sketched in a distributed environment, and then merged into a single sketch of the whole data set. In the last decade a variety of sketches have been developed that are non-mergeable, but attractive for other reasons. They are simpler, their cardinality estimates are strictly unbiased, and they have substantially lower variance. We evaluate sketching schemes on a reasonably level playing field, in terms of its MVP: Memory-Variance Product, i. e., the product of its space, in bits , and the relative variance of its estimates.