Existe-t-il un filtre anti-Bloom?

25

Un filtre Bloom permet de suivre efficacement si différentes valeurs ont déjà été rencontrées lors du traitement. Lorsqu'il existe de nombreux éléments de données, un filtre Bloom peut entraîner une économie de mémoire significative sur une table de hachage. La principale caractéristique d'un filtre Bloom, qu'il partage avec une table de hachage, est qu'il dit toujours "pas nouveau" si un élément n'est pas nouveau, mais il y a une probabilité non nulle qu'un élément soit marqué comme "pas nouveau" "même quand c'est nouveau.

Existe-t-il un "filtre anti-Bloom", qui a le comportement inverse?

En d'autres termes: existe-t-il une structure de données efficace qui dit "nouveau" si un article est nouveau, mais qui pourrait également dire "nouveau" pour certains articles qui ne sont pas nouveaux?

Garder tous les éléments précédemment vus (par exemple, dans une liste chaînée triée) satisfait la première exigence mais peut utiliser beaucoup de mémoire. J'espère que cela est également inutile, compte tenu de la deuxième condition assouplie.


Pour ceux qui préfèrent un traitement plus formel, écrivez b(x)=1 si le filtre Bloom pense que x est nouveau, sinon, et écrivez si est vraiment nouveau et sinon.n ( x ) = 1 x n ( x ) = 0b(x)=0n(x)=1xn(x)=0

Alors Pr[b(x)=0|n(x)=0]=1 ; Pr[b(x)=0|n(x)=1]=α ; Pr[b(x)=1|n(x)=0]=0; Pr[b(x)=1|n(x)=1]=1α , pour quelque 0<α<1 .

Je demande: existe-t-il une structure de données efficace, implémentant une fonction avec quelque 0 < β < 1 , telle que P r [ b ( x ) = 0 | n ( x ) = 0 ] = β ; P r [ b ( x ) = 0 | n ( x ) = 1 ] = 0 ; P rb0<β<1Pr[b(x)=0|n(x)=0]=βPr[b(x)=0|n(x)=1]=0Pr[b(x)=1|n(x)=0]=1β ; Pr[b(x)=1|n(x)=1]=1 ?


Edit: Il semble que cette question ait été posée auparavant sur StackExchange, car /programming/635728 et /cstheory/6596 avec une gamme de réponses de "ne peut pas être fait "à travers" peut être fait, à un certain coût "à" c'est trivial à faire, en inversant les valeurs de ". Il n'est pas encore clair pour moi quelle est la "bonne" réponse. Ce qui est clair, c'est qu'un schéma de mise en cache LRU d'une certaine sorte (comme celui suggéré par Ilmari Karonen) fonctionne plutôt bien, est facile à mettre en œuvre et a entraîné une réduction de 50% du temps nécessaire à l'exécution de mon code.b

András Salamon
la source
Pour une raison quelconque, je suis tenté de dire que cela est très similaire au problème que les algorithmes de mise en cache et de placement de cache tentent de résoudre. Considérez un cache utilisant le remplacement le moins fréquemment utilisé (LFU). Un algorithme de remplacement théoriquement optimal mais impossible serait d'expulser celui que vous ne reverrez pas plus longtemps, comme pour les caches. Je suppose que la mise en cache repose sur certaines hypothèses sur la nature de la distribution qui peuvent ne pas tenir généralement, mais cela vaut la peine de considérer si cela s'applique.
Patrick87
Vous pouvez être intéressé par la conférence suivante: Filtres d'appartenance aux ensembles basés sur la satisfaction
Kaveh
@Kaveh: merci pour le pointeur, va regarder.
András Salamon

Réponses:

12

En allant avec l'idée de hachage de Patrick87, voici une construction pratique qui répond presque à vos exigences - la probabilité de confondre faussement une nouvelle valeur avec une ancienne n'est pas tout à fait nulle, mais peut être facilement rendue négligeable.

Choisissez les paramètres et k ; les valeurs pratiques pourraient être, disons, n = 128 et k = 16 . Soit H une fonction de hachage cryptographique sécurisée produisant (au moins) n + k bits de sortie.nkn=128k=16Hn+k

Soit un tableau de 2 k chaînes de bits à n bits. Ce tableau stocke l'état du filtre, en utilisant un total de n 2 k bits. (Peu importe la façon dont ce tableau est initialisé; nous pouvons simplement le remplir de zéros ou de bits aléatoires.)a2k nn2k

  • Pour ajouter une nouvelle valeur au filtre, calculez ix , où i désigne les k premiersbits et j désigne les suivantsij=H(x)ikj bits suivants de H ( x ) . Soit a i = j .nH(x)ai=j

  • Pour tester si une valeur a été ajoutée au filtre, calculez i x , comme ci-dessus, et vérifiez si a i = j . Si oui, retournez vrai; sinon retournez false.ij=H(x)ai=j

Revendication 1: La probabilité d'un résultat faussement positif (= nouvelle valeur faussement prétendu avoir été vu) est . Cela peut être rendu arbitrairement petit, à un coût modeste en espace de stockage, en augmentant n ; en particulier, pour n 128 , cette probabilité est essentiellement négligeable, étant en pratique bien inférieure à la probabilité d'un faux positif dû à un dysfonctionnement matériel.1/2n+knn128

En particulier, après que valeurs distinctes ont été vérifiées et ajoutées au filtre, la probabilité qu'au moins un faux positif se soit produit est ( N 2 - N ) / 2 n + k + 1 . Par exemple, avec n = 128 et k = 16 , le nombre de valeurs distinctes nécessaires pour obtenir un faux positif avec une probabilité de 50% est d'environ 2 ( n + k ) / 2 = 2 72 .N(N2N)/2n+k+1n=128k=162(n+k)/2=272

Allégation 2: La probabilité d'un faux négatif (= valeur ajoutée précédemment prétendument nouvelle) n'est pas supérieure à , où N est le nombre de valeurs distinctes ajoutées au filtre (ou, plus précisément, le nombre de valeurs distinctes ajoutées après que la valeur spécifique testée a été ajoutée le plus récemment au filtre).1(12k)N1exp(N/2k)<N/2kN


Ps. Pour mettre «négligeable petit» en perspective, le cryptage 128 bits est généralement considéré comme incassable avec la technologie actuellement connue. Obtenir un faux positif de ce schéma avec est aussi probable que quelqu'un devine correctement votre clé de chiffrement secrète 128 bits lors de sa première tentative . (Avec n = 128 et k = 16 , il est en fait environ 65 000 fois moins probable que cela.)n+k=128n=128k=16

Mais si cela vous laisse encore une sensation de nervosité irrationnelle, vous pouvez toujours passer à ; cela doublera vos besoins de stockage, mais je peux vous parier en toute sécurité toute somme que vous voudriez nommer que personne ne verra jamais de faux positif avec n = 256 - en supposant que la fonction de hachage n'est pas rompue, de toute façon.n=256n=256

Ilmari Karonen
la source
1
Non seulement la probabilité peut être rendue comparable à celle d'un dysfonctionnement matériel; il peut également être rendu comparable à la probabilité que quelqu'un devine votre clé RSA pour la connexion SSH lors du premier essai . IMO ce dernier transmet la praticité de votre solution plus que le premier.
R ..
+1 Très bien - je crois comprendre que cela résout le problème d'efficacité de l'espace en permettant une (très petite) chance de répondre incorrectement "pas nouveau" lorsque l'article est, en fait, nouveau. Très pratique et bonne analyse.
Patrick87
1
La revendication 1 indique simplement qu'une fonction de hachage décente a une faible probabilité de collisions. Cela est déjà vrai en pratique si est au moins égal à 50 environ. Pour mon application, n = 44 et k = 20 fonctionne très bien avec une simple fonction de hachage 64 bits, non cryptographiquement sécurisée mais rapide. n+kn=44k=20
András Salamon
@ AndrásSalamon: Vrai, bien qu'une fonction de hachage cryptographique sécurisée fournisse en fait une garantie légèrement plus forte: à savoir, qu'il est impossible de trouver des entrées en collision même si vous essayez de les rechercher délibérément . Avec un suffisamment grand (par exemple n = 128 comme je l'ai suggéré ci-dessus), cela signifie que le stockage des données complètes n'est pas nécessaire même si le coût d'un faux positif est élevé et même si un adversaire actif tente d'en trouver un. Bien sûr, si vous n'avez pas besoin d'une garantie aussi forte, un risque de collision un peu plus élevé peut être acceptable. nn=128
Ilmari Karonen du
1
@Newtopian La raison pour laquelle j'ai spécifié une fonction de hachage cryptographique est que pour ceux-ci, il n'y a aucun moyen connu de générer des collisions plus efficacement que par force brute (c'est-à-dire en testant de nombreuses entrées et en sélectionnant celles qui entrent en collision), sinon le hachage serait considéré cassé (comme, disons, MD5 de nos jours). Ainsi, pour un hachage cryptographique, nous pouvons supposer assez sûrement que le taux de collision est le même que pour une fonction de hachage aléatoire idéale. L'utilisation d'une fonction de hachage universelle ou d'un MAC à clé (avec une clé secrète aléatoire) rendrait cette garantie encore plus forte.
Ilmari Karonen
8

Non, il n'est pas possible d'avoir une structure de données efficace avec ces propriétés, si vous voulez avoir la garantie que la structure de données dira "nouvelle" si elle est vraiment nouvelle (elle ne dira jamais, "jamais nouvelle" si il est en fait nouveau, aucun faux négatif autorisé). Une telle structure de données devra conserver toutes les données pour pouvoir répondre "pas nouveau". Voir la réponse de pents90 sur cstheory pour une justification précise.

En revanche, les filtres Bloom peuvent obtenir une garantie que la structure de données dira "pas nouveau" si elle n'est pas nouvelle, d'une manière efficace. En particulier, les filtres Bloom peuvent être plus efficaces que le stockage de toutes les données: chaque élément individuel peut être assez long, mais la taille du filtre Bloom évolue avec le nombre d'éléments, et non leur longueur totale. Toute structure de données pour votre problème devra évoluer avec la longueur totale des données, pas le nombre d'éléments de données.

jbapple
la source
Voir également la réponse acceptée, puisque la question est la même
Joe
-1 Vous devriez probablement qualifier ce que vous voulez dire lorsque vous dites que ce n'est pas possible. De toute évidence, il est possible de le faire efficacement, et il est également possible de le faire avec un faible taux d'erreur, donc trouver un certain équilibre dans une implémentation donnée devrait être possible ... en particulier, il serait utile d'expliquer exactement ce que l'on entend par "toutes les données jamais", car ce n'est pas strictement nécessaire pour répondre à la question posée. Les faux négatifs - répondre "nouveau" lorsque la réponse doit être "pas nouvelle" - sont autorisés ici, donc toutes les données ne doivent pas être conservées.
Patrick87
1
This answer is perfectly reasonable, and seems to address the letter of my question, but perhaps not the spirit.
András Salamon
@D.W. Thanks for taking the time to update the answer. I'm inclined to leave this as an answer now, although I still object to the language used when describing the inefficiency of anti-bloom filters, in addition to thinking it would be best to elaborate a bit more on the "details" referenced... leaving the -1 for now. Cleaned up some obsolete comments.
Patrick87
@DW Par "faux négatif", j'ai l'intention de répondre "nouveau" alors que la réponse aurait dû être "pas nouvelle". (Un peu contre-intuitivement, "pas nouveau" est le cas positif ici.) Vous n'avez pas besoin de sauvegarder "toutes les données jamais" pour le retirer, bien que je suis enclin à croire que vous devez sauvegarder des éléments entiers (juste pas tous les éléments - à moins que vous ne souhaitiez accepter une possibilité d'erreur hypothétiquement significative, conformément à l'autre réponse à la question ici.)
Patrick87
6

Et juste une table de hachage? Lorsque vous voyez un nouvel élément, consultez la table de hachage. Si l'emplacement de l'article est vide, retournez "nouveau" et ajoutez l'article. Sinon, vérifiez si la place de l'article est occupée par l'article. Si c'est le cas, retournez "pas nouveau". Si l'emplacement est occupé par un autre élément, retournez "nouveau" et écrasez l'emplacement avec le nouvel élément.

Vous obtiendrez certainement toujours correctement "Nouveau" si vous n'avez jamais vu le hachage de l'élément auparavant. Vous obtiendrez certainement toujours correctement "Pas nouveau" si vous n'avez vu le hachage de l'élément que lorsque vous avez vu le même élément. La seule fois où vous obtiendrez «Nouveau» lorsque la bonne réponse est «Pas nouveau» est si vous voyez l'élément A, puis voir l'élément B, puis voir à nouveau l'élément A, et les hachages A et B font la même chose. Surtout, vous ne pouvez jamais obtenir «Pas nouveau» de manière incorrecte.

Patrick87
la source
1
Je suppose que ce genre d'ignore le problème d'efficacité de l'espace, ou plutôt, est beaucoup moins efficace qu'un filtre de floraison, car un filtre de floraison n'a vraiment besoin que d'un peu par seau, et cela nécessite autant d'espace par seau qu'il en faut pour représenter les articles. Eh bien ... à moins que l'univers ne soit fini (comme dans la réponse de Wandering Logic), je pense que vous ne pouvez probablement pas être très proche de l'efficacité spatiale d'un filtre de floraison.
Patrick87
Personnellement, je pense que votre réponse est bien meilleure que la mienne. Un filtre de floraison n'est pas seulement un peu par seau si vous voulez des probabilités supérieures à 50%. C'est également une taille fixe et une fois que vous le remplissez à plus de la moitié, la probabilité de faux positifs augmente brusquement. Il n'y a aucun moyen pratique de l'étendre, aucun moyen pratique de l'utiliser comme cache et aucun moyen pratique de supprimer des éléments. Je prendrai une table de hachage à chaque fois.
Wandering Logic
@WanderingLogic L'utilisation d'un petit compteur saturant au lieu d'un seul bit permet de prendre en charge la suppression (au prix de la capacité et uniquement si le compteur n'est pas au maximum, évidemment).
Paul A. Clayton
4

Dans le cas où l'univers des éléments est fini, alors oui: utilisez simplement un filtre de floraison qui enregistre quels éléments sont hors de l'ensemble, plutôt que dans l'ensemble. (C'est-à-dire, utilisez un filtre de floraison qui représente le complément de l'ensemble d'intérêt.)

Un endroit où cela est utile est d'autoriser une forme limitée de suppression. Vous gardez deux filtres de floraison. Ils commencent vides. Lorsque vous insérez des éléments, vous les insérez dans le filtre de floraison A. Si vous souhaitez par la suite supprimer un élément, vous insérez cet élément dans le filtre de floraison B. Il n'y a aucun moyen d'annuler la suppression. Pour effectuer une recherche, vous effectuez d'abord une recherche dans le filtre de floraison A. Si vous ne trouvez aucune correspondance, l'élément n'a jamais été inséré (avec probabilité 1). Si vous trouvez une correspondance, l'élément peut (ou non) avoir été inséré. Dans ce cas, vous effectuez une recherche dans le filtre de floraison B. Si vous ne trouvez aucune correspondance, l'élément n'a jamais été supprimé. Si vous trouvez une correspondance dans le filtre de floraison B, l'élément a probablement été inséré, puis supprimé.

Cela ne répond pas vraiment à votre question, mais, dans ce cas limité, le filtre de floraison B exécute exactement le comportement de "filtre anti-floraison" que vous recherchez.

Les chercheurs sur le filtre Real Bloom utilisent des moyens beaucoup plus efficaces de représenter la suppression, voir la page de la publication de Mike Mitzenmacher .

Logique errante
la source
Dans cette question, nous traitons des articles et il n'y a aucune suppression. Il n'y a aucun moyen significatif de stocker le compliment sans avoir à retirer les éléments du filtre de floraison
Joe
1
@Joe: Je suis d'accord que le problème est insoluble en général, j'ai donc limité ma réponse au cas où le complément était fini et petit.
Wandering Logic
1

Je veux juste ajouter ici, que si vous êtes dans une situation chanceuse, que vous connaissez toutes les valeurs vjeque vous pourriez voir; alors vous pouvez utiliser un filtre de floraison de comptage.

Un exemple pourrait être les adresses IP, et vous voulez savoir à chaque fois que vous en voyez une que vous n'avez jamais vue auparavant. Mais c'est toujours un ensemble fini, donc vous savez à quoi vous attendre.

La solution réelle est simple:

  1. Ajoutez tous vos articles au filtre de comptage des fleurs.
  2. Lorsque vous voyez un nouvel élément, il aura des valeurs 1 dans tous les emplacements.
  3. Après avoir vu un nouvel élément réel, soustrayez-le du filtre.

Vous pouvez donc avoir des valeurs de «faux positifs» qui étaient en fait anciennes, mais reconnues comme nouvelles. Cependant, vous n'obtiendrez jamais «pas nouveau» pour une nouvelle valeur, car sa valeur sera toujours dans tous les emplacements, et personne d'autre n'aurait pu l'enlever.

Thomas Ahle
la source