Calcul de la population approximative d'un filtre de bloom

Question

Pour un filtre de bloom de taille N-bits et K fonctions de hachage, les bits M (où M < = N) du filtre sont définis.

Est-il possible d'approximer le nombre d'éléments insérés dans le filtre bloom?

Exemple simple

J'ai ressassant l'exemple suivant, en supposant un BF 100 bits et 5 fonctions de hachage où 10-bits sont ...

Meilleur scénario: En supposant que les fonctions de hachage sont vraiment parfaites et mappent un peu pour un certain nombre de valeurs X, alors 10 bits ont été définis, nous pouvons dire qu'il n'y a que 2 éléments insérés dans le BF

Dans le pire des scénarios: En supposant les fonctions de hachage sont mauvaises et uniformément mapper au même bit (encore unique entre eux), alors nous pouvons dire que 10 éléments ont été insérés dans le BF

La plage semble être [2,10] où abouts dans cette gamme est probablement déterminée par la probabilité de faux-positif - I suis coincé à ce stade.

Answer 1

Cette question m'inquiète un peu car il y a better algorithms pour compter approximativement le nombre d'éléments distincts avec de petites quantités de stockage. Néanmoins, si nous devons utiliser un filtre Bloom, supposons que les fonctions de hachage sont des oracles aléatoires (toutes les valeurs choisies indépendamment, ou "vraiment parfait", à ne pas confondre avec un hachage parfait). Maintenant, nous avons un problème de balles et de bacs: étant donné que M de N contenait des balles, combien de balles avons-nous lancées? Soit B le nombre de balles lancées; le nombre d'articles est B/K, puisque pour chaque article nous jetons K balles.

L'approximation standard pour les processus de balles et de boîtes consiste à modéliser chaque casier comme un processus de Poisson indépendant; le temps avant que la poubelle ne soit occupée est exponentiellement distribué. En laissant 1 être le temps qu'il faut pour lancer toutes les billes, l'estimation du maximum de vraisemblance λ du taux de cette distribution exponentielle vérifie Pr(Exponential[λ] < 1) = M/N, donc 1 - exp(-λ) = M/N et λ = -log(1 - M/N). Le paramètre λ s'apparente au nombre de billes, donc l'estimation pour le nombre d'articles est B ≈ -N log(1 - M/N)/K.

EDIT: Il y a N cases, donc nous devons multiplier par N.

Answer 2

L'entrée à Wikipedia vous donne une formule pour la probabilité d'un bit particulier étant défini, en supposant que les fonctions de hachage rendent tout aléatoire. C'est 1 - (1-1/m)^kn. Comme il y a m bits dans le filtre, cela signifie que le nombre de bits attendu/moyen sera m(1-(1-1/m)^kn). Donc, vous pouvez trouver une estimation raisonnablement plausible pour n en choisissant le n qui le rend égal au nombre de bits réellement défini. Pour avoir une idée de la précision d'une telle supposition, il serait bon d'avoir une idée de la variance du nombre de bits mis en place. Vous pouvez le faire exactement, mais c'est une douleur dans le cou. Vous pouvez utiliser le fait que Var(X) = E(X^2) - E(X)^2.Dans ce cas, E(X^2) dépend principalement de la probabilité que les paires de bits soient toutes deux définies, et vous pouvez calculer cela en considérant la probabilité des instructions comme "bit 0 est défini et le bit 1 est clair et tous les autres bits sont clairs" et "bit 0 est clair" et "tous les bits sauf 0 et 1 sont clairs".