Je n'arrive pas à comprendre les problèmes possibles de Bloom Filter avec les jeux dynamiques.Bloom Filtres Problèmes possibles lors de l'utilisation de jeux dynamiques
Pouvez-vous me parler de certains problèmes pouvant survenir lors de l'ajout/du retrait d'éléments de l'appareil?
Le problème principal est que les filtres bloom ne sont pas conçus pour être retirés.
Par exemple. Supposons
h1(x) = x %5
h2(x) = (x+2) % 5
Et vous avez 2 éléments compte dans l'ensemble: 2,4.
Vous avez le bitset:
bitset = { 0, 1, 1, 0, 1 }
Maintenant, vous voulez supprimer 2 de l'ensemble. Comment faites-vous? Vous avez aucune idée que BITSET [4] est commun aux deux éléments, et une fois que vous le retirez, vous obtiendrez la nouvelle bitset:
bitset' = { 0, 0, 1, 0, 0 }
Mais maintenant, si vous essayez de vérifier si 4 est en elle, vous vont obtenir une mauvaise réponse.
Une solution possible pour permettre l'enlèvement des filtres bloom est counting bloom filters, mais il a aussi ses négatifs. Un autre problème, si votre ensemble est dynamique et peut continuer à croître, il n'est pas trivial d'augmenter sa taille. Vous ne pouvez pas simplement allouer le double de l'espace, et rehash toute la collection, vous n'avez aucune idée de ce que les éléments d'origine étaient.
Ainsi, le filtre de bloom est utilisé lorsque sa taille est connue (ou limitée) a priori.