Bloom Filter
Un filtre de Bloom approxime l'appartenance à un ensemble avec k fonctions de hachage et un tableau de bits, offrant une efficacité spatiale au prix d'un taux de faux positifs.
Objectif
Fournir des requêtes d'appartenance approximatives et économes en espace pour les caches et les bases de données.
Mécanisme
Insertion : on hache l'élément avec k fonctions et l'on positionne les bits correspondants. Requête : si les k bits valent 1, l'élément est probablement présent (taux de faux positifs p≈(1-e^(-kn/m))^k). Ne produit jamais de faux négatifs. La suppression n'est pas prise en charge dans la version standard.
Cas d’usage
- Filtrage de cache
- Optimisation de requêtes de bases de données
- Déduplication