I'm trying to implement an online distinct counting algorithm, and I have thousands of small sets of 32 bit IP addresses whose sizes I want to estimate with high accuracy (1-5%).
I came across quite a few algorithms such as linear counting$^1$, PCSA$^2$, HyperLogLog$^3$ etc. According to their papers, their space needed varies with relative error as $1/\epsilon^2$. For my purpose, this seems really wasteful e.g., PCSA needs > 10,000 bits when the set size is 50 and $\epsilon$ is 1%.
Is there any reason why in practice, we may not need that many bits? Is there any algorithm that uses little space to estimate the size of small sets with high accuracy?
Thanks!
References:
[1] Linear Counting: Kyu-Young Whang, Brad T. Vander-Zanden, and Howard M. Taylor. 1990. A linear-time probabilistic counting algorithm for database applications. ACM Trans. Database Syst. 15, 2 (June 1990), 208-229. DOI=10.1145/78922.78925 http://doi.acm.org/10.1145/78922.78925
[2] PCSA: Philippe Flajolet and G. Nigel Martin. 1985. Probabilistic counting algorithms for data base applications. J. Comput. Syst. Sci. 31, 2 (September 1985), 182-209. DOI=10.1016/0022-0000(85)90041-8 http://dx.doi.org/10.1016/0022-0000(85)90041-8
[3] HyperLoglog: the analysis of a near-optimal cardinality estimation algorithm, by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier. Proceedings of the AofA07 Conference (Analysis of Algorithms-2007), published in Discrete Mathematics and Theoretical Computer Science (DMTCS) Proceedings, vol AH, pp. 127--146 (2007).