Streaming Les algorithmes et filtres Bloom - les nuls

Les filtres Bloom sont au cœur de nombreux algorithmes de streaming. Créé il y a près de 50 ans par Burton H. Bloom, à une époque où l'informatique était encore très jeune, l'intention originale du créateur de cet algorithme était d'échanger espace (mémoire) et / ou temps (complexité) contre ce qu'il appelait erreurs admissibles Son document original s'intitule Compromis espace / temps dans le codage de hachage avec erreurs admissibles.

Vous pouvez vous interroger sur l'espace et le temps que Bloom considère comme des facteurs de motivation pour son algorithme. Imaginez que vous deviez déterminer si un élément est déjà apparu dans un flux en utilisant une structure de données précédemment discutée. Trouver quelque chose dans un flux implique que l'enregistrement et la recherche sont rapides, donc une table de hachage semble un choix idéal. Les tables de hachage nécessitent simplement l'ajout des éléments que vous souhaitez enregistrer et les stocker. Récupérer un élément à partir d'une table de hachage est rapide car la table de hachage utilise des valeurs facilement manipulées pour représenter l'élément, plutôt que l'élément lui-même (ce qui pourrait être assez complexe). Pourtant, stocker à la fois les éléments et un index à ces éléments a des limites. Si une table de hachage fait face à plus d'éléments qu'elle ne peut en supporter, tels que les éléments d'un flux continu et potentiellement infini, vous finirez par rencontrer des problèmes de mémoire à un moment donné.

Une considération essentielle pour les filtres de Bloom est que les faux positifs peuvent se produire, mais les faux négatifs ne le peuvent pas. Par exemple, un flux de données peut contenir des données de surveillance en temps réel pour une centrale électrique. Lors de l'utilisation d'un filtre Bloom, l'analyse du flux de données montrerait que les lectures attendues font probablement partie de l'ensemble des lectures autorisées, certaines erreurs étant autorisées. Cependant, lorsqu'une erreur se produit dans le système, la même analyse montre que les lectures ne font pas partie de l'ensemble des lectures autorisées. Les faux positifs sont peu susceptibles de causer des problèmes, mais l'absence de faux négatifs signifie que tout le monde reste en sécurité. En raison de la possibilité de faux positifs, les filtres tels que le filtre Bloom sont des structures de données probabilistes - ils ne fournissent pas une réponse certaine mais probable.

Les hachages, les entrées individuelles d'une table de hachage, sont rapides car ils agissent comme l'index d'un livre. Vous utilisez une fonction de hachage pour produire le hachage; l'entrée est un élément contenant des données complexes, et la sortie est un nombre simple qui agit comme un indice pour cet élément. Une fonction de hachage est déterministe car elle produit le même nombre chaque fois que vous l'alimentez avec une entrée de données spécifique.Vous utilisez le hachage pour localiser les informations complexes dont vous avez besoin. Les filtres Bloom sont utiles car ils constituent un moyen frugal d'enregistrer les traces de nombreux éléments sans avoir à les stocker comme le fait une table de hachage. Ils fonctionnent de manière simple et utilisent les éléments suivants comme ingrédients principaux:

• Un vecteur de bit: Une liste d'éléments binaires, où chaque bit de l'élément peut avoir une valeur de 0 ou 1. La liste est longue nombre de bits appelés m. Plus m est grand, mieux c'est, bien qu'il existe des moyens de définir de manière optimale sa taille.
• Une série de fonctions de hachage: Chaque fonction de hachage représente une valeur différente. Les fonctions de hachage peuvent rapidement croquer des données et produire des résultats uniformément distribués, dont les résultats vont du minimum au maximum des valeurs de sortie du hachage.