- Filtre de bloom
-
Filtre de Bloom
Le filtre de Bloom, conçu par Burton H. Bloom en 1970, est une structure de données probabiliste qui optimise l'espace utilisé. Cette structure est utilisée pour tester si un élément fait partie d'un ensemble.
Il permet notamment d'optimiser les flux entre pairs dans un réseau informatiques pairs à pairs (Gnutella).
Liens externes
- C++ and Object Pascal Bloom Filter Implementation
- Original paper
- Less Hashing, Same Performance: Building a Better Bloom Filter
- Table of false-positive rates for different configurations
- Online Bloom filter calculator
- Bloom filters in Python
- Bloom filters in Perl
- Network Applications of Bloom Filters: A Survey. A. Broder and M. Mitzenmacher. Allerton Conference 2002.
- Spectral Bloom Filters. S. Cohen and Y. Matias. SIGMOD 2003.
- The Bloomier Filter: An Efficient Data Structure for Static Support Lookup Tables. B. Chazelle, J. Kilian, R. Rubinfeld, and A. Tal. SODA 2004.
- An Optimal Bloom Filter Replacement; In Proc. ACM-SIAM Symposium on Discrete Algorithms, SODA 2005
- Mutable strings in Java: Design, implementation and lightweight text-search algorithms; In Sci. Comput. Programming, 54(1):3–23, 2005.
- Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol
- Bloom filters in the microprocessor, Micro 2004
- Packet scanning using Bloom filters
- Retouched Bloom Filters: Allowing Networked Applications to Flexibly Trade Off False Positives Against False Negatives. Donnet et al. CoNEXT 2006.
- Generalized Bloom Filters Paper Webpage
- High-Speed Dynamic Packet Filtering using Bloom filters in the Linux Kernel. GPL2-licensed paper.
- Hierarchical Bloom filters. Allows for compact storage and query of large bit streams.
Portail de l’informatique
Catégorie : Structure de données
Wikimedia Foundation. 2010.
