Better Cardinality Estimators for HyperLogLog, PCSA, and Beyond
Dingyu Wang, Seth Pettie · 2023
Cardinality Estimation (aka Distinct Elements) is a classic problem in sketching with many applications in databases, networking, and security. Although sketching algorithms are fairly simple, analyzing the cardinality estimators is notoriously difficult, and even today the analyses of state-of-the-art sketches like HyperLogLog and ¶CSA are not very accessible.