4 citations · 4 across the 4 of their papers we have counts for
Showing 2020Show all
2 papers · 1 filter
cs.DS2020
Non-Mergeable Sketching for Cardinality Estimation
Seth Pettie, Dingyu Wang, Longhui Yin
Cardinality estimation is perhaps the simplest non-trivial statistical problem that can be solved via sketching. Industrially-deployed sketches like HyperLogLog, MinHash, and PCSA…
cs.DS2020★ 4 cited
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…