Bloom filter

Le Bloom filter, a été pensé par Burton H.Bloom en 1970. C'est une structure de données, probabiliste, compacte en mémoire, qui est utilisée pour renseigner si un élément est présent ou non dans un ensemble. Les false positives sont possibles mais pas les false negatives. Les élements peuvent uniquement être ajoutés au set, ils ne peuvent pas être enlevés. Plus il y a d'élements dans le set, plus la probablilité d'avoir des false positives est grande.

Le Bloom filter peut être utilisé ainsi dans de nombreuses situations : détection de la langue en vérifiant l'appartenance à un dictionnaire, marquage d'urls pour les crawlers afin de ne pas visiter deux fois les mêmes pages, etc.

• Des compléments sur le bloom filter sur Wikipedia.
• Utiliser des bloom en perl.
• Ajuster ces paramètres.