6
$\begingroup$

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).

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ How are these sets represented? $\:$ (I can't think of any way that doesn't make the problem trivial.) $\endgroup$ – user6973 Aug 12 '12 at 20:46
  • $\begingroup$ It's a streaming problem. You could say I'm monitoring packets on a link, so I see a stream of packets like <srcip:10.3.4.2, set:3>, <srcip:10.2.1.5, set:1> etc. I'm not assuming anything about the distribution of the IP addresses in a set, or across the sets. $\endgroup$ – nia Aug 12 '12 at 21:03
  • 5
    $\begingroup$ Theoretically speaking, $\epsilon^{-2}$ is necessary in the worst case. There is a recent optimal algorithm, but I have some doubts if it is ready for practice. There is a chance that the worst case analysis is too pessimistic for your data, so maybe you should play with the parameters of Flajolet-Martin. There are also practical studies that exploit domain knowledge, e.g. this one $\endgroup$ – Sasho Nikolov Aug 13 '12 at 0:32
-3
$\begingroup$

2^32 is only 4 billion; and doubtful you will saturate even a small fraction of that if you are watching IPs. Just store it all. A radix tree will compact as it saturates since you can flag entire subdomains as saturated.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.