Information Theoretic Limits of Cardinality Estimation: Fisher Meets Shannon

Seth Pettie, Dingyu Wang

Estimating the cardinality (number of distinct elements) of a large multiset is a classic problem in streaming and sketching. In this paper we study the intrinsic tradeoff between…