Filtre de Bloom

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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.

Principe[modifier | modifier le code]

Proportion de faux-positifs[modifier | modifier le code]

Il est possible d'évaluer la proportion de faux-positifs en fonction de divers paramètres. Ainsi, si l'on considère une fonction de hachage qui choisit un élément de l'ensemble de manière équiprobable, et que m représente le nombre de bits dans cet ensemble, et que k représente le nombre de fonctions de hachage, alors la probabilité qu'un bit donné soit inscrit à 0 par une fonction de hachage donnée vaut f = 1 - {1 \over m}.

Si l'on généralise ceci à l'ensemble des fonctions de hachage considérées, alors cette probabilité devient f = \left (1-{1 \over m}\right )^k.

Si l'on considère à présent que ce filtre reçoit n éléments (chaînes de caractères...), la probabilité qu'un bit donné vaille 0 vaut f = \left (1 - {1 \over m}\right )^{kn}. On en déduit que la probabilité que ce bit vaille 1 est 
f = 1 - \left (1 - {1 \over m}\right )^{kn}

Ainsi, si l'on teste la probabilité de présence d'un élément qui n'est pas dans l'ensemble, chaque position k possède la probabilité ci-dessus de valoir 1. La probabilité que tous les k vaillent 1 (déclenchant un faux-positif) découle des calculs précédents : 
\left (1 - \left[ 1 - {1 \over m}\right] ^{nk}\right) ^k \approx \left (1 - e^{{-kn\over m}}\right )^k

Implémentation[modifier | modifier le code]

Applications[modifier | modifier le code]

Ce genre de filtre permet d'éviter des appels inutiles à une très grande base de données en vérifiant tout de suite qu'une ligne recherchée n'y est pas présente. Le filtre n'étant pas parfait, la recherche inutile aura toutefois lieu dans certains cas, mais une grande partie sera néanmoins évitée, multipliant ainsi le nombre de requêtes utiles possibles à matériel donné. Cette méthode est utilisée par Google dans leur base de données distribuées, BigTable [1]. Ce type de filtre est également utilisé pour réaliser de l'inspection de paquets en profondeur[2], en vertu des raisons citées plus haut. Leur implémentation au niveau matériel a permis de réaliser de l'inspection de paquets en profondeur à la vitesse du réseau.

Elle permet aussi d'optimiser les flux entre pairs dans un réseau informatiques pairs à pairs, comme Gnutella.

Références[modifier | modifier le code]

  1. Bigtable: A Distributed Storage System for Structured Data
  2. Deep packet Inspection using parallel Bloom Filters

Bibliographie[modifier | modifier le code]

  • Burton H. Bloom, « Space/Time Trade-offs in Hash Coding with Allowable Errors », Commun. ACM, vol. 13, no 7,‎ 1970, p. 422-426 (présentation en ligne)

Liens externes[modifier | modifier le code]