L'index du filtre et les fonctions Hash dans Bloom Filter

Le filtre Bloom utilise un tableau de bits de m bits, donc il y a 0 à m-1 index dans le tableau mais les fonctions de hachage que j'utilise renvoient un hachage 32 bits, donc il pourrait de 0 à (2^32) -1 étant donné que le hachage est utilisé comme indice pour le tableau de bits (filtre), il est tout à fait possible que le hachage soit supérieur à m, par conséquent la valeur ne sera pas mappée sur le tableau de bits . Dois-je prendre le mod du hash i.e hachage% m de sorte que le hachage résultant doit correspondre à un index dans le tableau de bits. Va-t-il augmenter le nombre de faux positifs (IMO ça va)?L'index du filtre et les fonctions Hash dans Bloom Filter

Source

2014-09-16 Abdullah Saleem

Ne pas faire mod. Utilisez simplement les premiers m bits de la fonction de hachage. Les chances d'un faux positif dépendent du nombre de bits que vous utilisez, mais aussi de l'espace utilisé. Le but d'un filtre bloom est de choisir le compromis. – btilly

Une fonction de hachage h: S -> uint est vaguement définie comme étant celle qui présente un degré élevé d'entropie sur l'ensemble S. Supposons que j'ai une certaine fonction de hachage h qui a une entropie très élevée sur S, mais pour laquelle la sortie h(x) pour x dans S est toujours pair. Cette restriction signifie simplement qu'un bit de la sortie de h est gaspillé, ce qui est seulement 1/32 des bits.

Supposons maintenant que j'ai un filtre Bloom pour lequel m est un nombre pair. Alors h(x) % m sera toujours un nombre pair - ce qui signifie seulement la moitié des bits du filtre Bloom seront utilisés! C'est mauvais!

Comme d'autres l'ont suggéré, en prenant simplement les premiers m bits de h(x) comme un index dans 2^m bacs de filtre Bloom est une meilleure stratégie, parce que, en supposant que vous étant donné une fonction de hachage qui présente un degré élevé d'entropie sur la set S, la fonction de hachage "premier m bits" g(x) = h(x)[0:m-1] devrait présenter une quantité presque proportionnelle d'entropie.

Source

2014-09-17 02:07:19

okay. si j'utilise les premiers ** n ** bits d'un hachage dans ce cas la taille du tableau de bits devrait être ** 2^n ** ie l'index maximum serait ** (2^n) -1 ** que chaque hash possible est un index valide? –

@AbdullahSaleem Pour un filtre Bloom avec des cases '2^m', vous utiliseriez les premiers bits' m' de 'h (x)', interprétés comme un entier binaire non signé, comme index dans les cases du filtre Bloom. –

c'est compris mais que se passe-t-il si la longueur du filtre Bloom n'est pas ** 2^m **. par exemple, la longueur du filtre bloom est ** 50 **. Je ne peux pas utiliser les ** 5 premiers bits ** parce que le hachage résultant serait de ** 0-31 ** et je ne peux pas utiliser d'abord ** 6 bits ** car dans ce cas le hachage résultant serait de ** 0-63 ** –

Oui, l'utilisation de mod augmente la probabilité de faux positifs. Stephan T. Lavavej avait un grand discours à ce sujet sur GoingNative 2013 (mod qui crée le biais), Voir HERE

Sa mention aussi sur (ce @btilly) a dit: il est préférable de couper simplement les bits - si le vôtre fonction de hachage C'est bon alors c'est OK.

Source

2014-09-16 19:28:38 Dawid

L'index du filtre et les fonctions Hash dans Bloom Filter

Répondre

Questions connexes