Title: Back to the Future: an Even More Nearly Optimal Cardinality Estimation Algorithm,
Abstract: We describe a new cardinality estimation algorithm that is extremely
space-efficient. It applies one of three novel estimators to the compressed
state of the Flajolet-Martin-85 coupon collection process. In an
apples-to-apples empirical comparison against compressed HyperLogLog sketches,
the new algorithm simultaneously wins on all three dimensions of the
time/space/accuracy tradeoff. Our prototype uses the zstd compression library,
and produces sketches that are smaller than the entropy of HLL, so no possible
implementation of compressed HLL can match its space efficiency. The paper's
technical contributions include analyses and simulations of the three new
estimators, accurate values for the entropies of FM85 and HLL, and a
non-trivial method for estimating a double asymptotic limit via simulation.