Filtre de Bloom
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant l’informatique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
|
Un filtre de Bloom est une structure de données probabiliste compacte inventée par Burton Howard Bloom en 1970.
Lors du test de la présence d'un élément dans un ensemble, un filtre de Bloom permet de savoir :
- avec certitude que l'élément est absent de l'ensemble (il ne peut pas y avoir de faux négatif) ;
- avec une certaine probabilité que l'élément peut être présent dans l'ensemble (il peut y avoir des faux positifs).
La taille d'un filtre de Bloom est fixe et indépendante du nombre d'éléments contenus (la structure peut donc être extrêmement compacte). Il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure.
[modifier] Implémentation
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !
[modifier] Applications
Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue !
Il permet notamment d'optimiser les flux entre pairs dans un réseau informatiques pairs à pairs (Gnutella).
