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. C'est une implémentation du type abstrait Ensemble.

Cette structure est probabiliste, c'est-à-dire qu'elle utilise des probabilités, et que sa correction est probabiliste. Plus précisément, 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, ce qui est remarquable, et en fait une structure très compacte. L'inconvénient est toutefois qu'il y a d'autant plus de faux positifs qu'il y a d'éléments dans la structure. Le principe du filtre est le même que pour le hachage.

Elle a été inventée par Burton Howard Bloom en 1970.

Description[modifier | modifier le code]

Un filtre de Blum est une structure de donnée qui peut être décrite par ses composantes et les opérations qu'elle supporte[1].

Composition[modifier | modifier le code]

Soit P l'ensemble de tous les éléments que pourraient contenir l'ensemble considéré. Par exemple, P est l'ensemble des entiers sur 32 bits, ou un ensemble de mots. Le filtre a deux composantes[2] :

  • T : un tableau booléen (on dira 0 et 1) de taille m dont chaque case est initialisée à 0. (indexé de 1 à m)
  •  : k fonctions de hachage de .

Opérations[modifier | modifier le code]

Un exemple de filtre de Bloom de l'ensemble (x, y, z). Les flèches de couleurs indiquent les bits qui correspondent à cet élément. On peut tester le fait que l'élément w n'appartient pas à l'ensemble, car tous ses bits ne sont pas à 1.

L'ajout d'un élément se fait en mettant à 1 chaque case d'indice dans le tableau T pour i variant de 1 à k.

La requête d'un élément consiste à vérifier si toutes les cases d'indices (i variant entre 1 et k) sont à 1 dans le tableau T. Cette étape peut renvoyer vrai alors que l'élément est absent, c'est un faux positif.

Le retrait d'un élément n'est pas possible.

Propriétés[modifier | modifier le code]

Espace mémoire[modifier | modifier le code]

Le filtre de Bloom utilise un espace constant. C'est son principal intérêt.

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 laissé à 0 par une fonction de hachage donnée vaut .

Si l'on généralise ceci à l'ensemble des fonctions de hachage considérées, alors cette probabilité devient .

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 . On en déduit que la probabilité que ce bit vaille 1 est

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. Si l'on suppose (et cette supposition est fausse) que ces événements sont indépendants, la probabilité que tous les k vaillent 1 (déclenchant un faux-positif) découle des calculs précédents :

La formule ci-dessus suppose que la probabilité que chaque bit vaille 1 est indépendante des autres bits, ce qui est faux, et peut mener à des résultats significativement différents quand est élevé[3]. Au contraire, quand le rapport est faible, le taux d'erreur tend effectivement vers la valeur ci-dessus.

La formule exacte est significativement plus complexe, et vaut :

Cette valeur peut être calculée récursivement. Cependant, peut être plus simple de faire appel à l'encadrement suivant, donné par Bose et al. [4] :

Utilisations[modifier | modifier le code]

Bases de données[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[5].

Inspection de paquets[modifier | modifier le code]

Ce type de filtre est également utilisé pour réaliser de l'inspection de paquets en profondeur[6], 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.

Flux pair à pair[modifier | modifier le code]

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

Rendu HTML[modifier | modifier le code]

Ce filtre est utilisé dans les moteurs de rendu HTML pour augmenter les performances des sélecteurs CSS[8].

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

  1. « Bloom filters, streaming algorithms, the count-min sketch », sur Université d'Illinois, .
  2. Antoine Genitrini, « Algorithmique avancée : Méthode de hachage », sur Université Pierre et Marie Curie, .
  3. (en) Ken Christensen, Allen Roginsky, Miguel Jimeno, « A new analysis of the false positive rate of a Bloom filter », Information Processing Letters, vol. 110, no 21,‎ , p. 944-949 (lire en ligne).
  4. (en) Prosenjit Bose, Hua Guo, Evangelos Kranakis, Anil Maheshwari, Pat Morin, Jason Morrison, Michiel Smid, Yihui Tang, « On the false-positive rate of Bloom filters », Information Processing Letters, vol. 108, no 4,‎ , p. 210-213 (lire en ligne).
  5. Fay Chang, Jeffrey Dean, Sanjay Ghemawat, Wilson C Hsieh, Deborah A Wallach, Mike Burrows, Tushar Chandra, Andrew Fikes  et Robert E Gruber, « Bigtable: A distributed storage system for structured data, », ACM Transactions on Computer Systems (TOCS), ACM, vol. 26, no 2,‎ , p. 4 (lire en ligne)
  6. Deep packet Inspection using parallel Bloom Filters
  7. Sasu Tarkoma, « Overlay and P2P Networks Unstructured networks », .
  8. (en) Nicole Sullivan, « CSS Selector Performance has changed! (For the better) », sur Performance Calendar, .

Bibliographie[modifier | modifier le code]

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

Liens externes[modifier | modifier le code]