Efficient estimation of the cardinality of large data sets
arXiv:math/0701347
Abstract
F.Giroire has recently proposed an algorithm which returns the approximate number of distincts elements in a large sequence of words, under strong constraints coming from the analysis of large data bases. His estimation is based on statistical properties of uniform random variables in . In this note we propose an optimal estimation, using Kullback information and estimation theory.
Extended and improved version of the published paper