Information theoretic limits of cardinality estimation: Fisher meets Shannon

Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching, dating back to Flajolet and Martin's classic Probabilistic Counting (PCSA) algorithm from 1983. In this paper we study the intrinsic tradeoff between the space complexity of the sketch and its estimation error in the random oracle model. We define a new measure of efficiency for data sketches called the Fisher-Shannon (FiSh) number H/I. It captures the tension between the limiting Shannon entropy (H) of the sketch and its normalized Fisher information (I) that characterizes the variance of a statistically efficient, asymptotically unbiased estimator. Our aim in introducing the FiSh-number is to build the mathematical machinery necessary to argue for precise optimality, rather than asymptotic optimality, up to large constant factors. Our results are as follows. • We prove that all base-q variants of Flajolet and Martin's PCSA sketch have FiSh-number H 0 /I 0 ≈ 1.98016 and that every base-q variant of (Hyper)LogLog has FiSh-number worse than H 0 /I 0 , but that they tend to H 0 /I 0 in the limit as q → ∞. Here H 0 , I 0 are precisely defined constants. This result reverses the common conception that HyperLogLog was a strict improvement over PCSA.