sketches-intro

Introductory Jupyter notebook on probabilistic data structures applied to network traffic analysis.

• Bitmap — exact membership for small universes
• Bloom Filter — approximate membership with controlled false positive rate
• Count-Min Sketch — approximate frequency counting for data streams

Synthetic stream of 1,000,000 packets with Zipf-distributed destination IPs (α=1.3), replicating real backbone traffic behavior.

pip install numpy matplotlib jupyter

jupyter notebook sketches-intro.ipynb

• Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors. Communications of the ACM.
• Cormode, G., & Muthukrishnan, S. (2005). An improved data stream summary: the count-min sketch. Journal of Algorithms.

Departamento de Informática — Universidade Federal do Espírito Santo (Ufes)