<p>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. </p>

CC BY-SA 3.0
2013-08-16T17:22:27.420Z
2013-08-16T17:22:27.420Z
Chad Brewbaker
<p>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%). </p>

<p>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%. </p>

<p>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? </p>

<p>Thanks!</p>

<p>References:</p>

<p>[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 <a href="http://doi.acm.org/10.1145/78922.78925">http://doi.acm.org/10.1145/78922.78925</a></p>

<p>[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 <a href="http://dx.doi.org/10.1016/0022-0000(85)90041-8">http://dx.doi.org/10.1016/0022-0000(85)90041-8</a></p>

<p>[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).</p>

CC BY-SA 3.0
2012-08-12T21:03:59.687Z
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.
nia
CC BY-SA 3.0
2012-08-13T00:32:52.180Z
Theoretically speaking, $\epsilon^{-2}$ is necessary in the worst case. There is a recent [optimal algorithm](http://www.almaden.ibm.com/cs/people/dpwoodru/knw11.pdf), 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](http://dl.acm.org/citation.cfm?id=1217709)
Sasho Nikolov
<db.databases><online-algorithms><ni.networking-internet>
What are good set size estimation algorithms for small sets (around 10-50 elements)?
nia
# What are good set size estimation algorithms for small sets (around 10-50 elements)?

(Asked by: username_0 on 2012-08-12)

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

**Tags:** db.databases, online-algorithms, ni.networking-internet

> **Comments:**
> **username_0**: 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.  
> **username_1**: Theoretically speaking, $\epsilon^{-2}$ is necessary in the worst case. There is a recent [optimal algorithm](http://www.almaden.ibm.com/cs/people/dpwoodru/knw11.pdf), 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](http://dl.acm.org/citation.cfm?id=1217709)  

---

## 1 answers

### Answer by username_2 on 2013-08-16. Score: -3

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.


---

