Un ensemble probabiliste sans faux positifs?

35

Ainsi, les filtres de Bloom sont plutôt sympas - ce sont des ensembles qui prennent en charge la vérification d’appartenance sans faux négatifs, mais avec une petite chance d’un faux positif. Récemment cependant, je voulais un "filtre de Bloom" qui garantisse le contraire: pas de faux positifs, mais potentiellement de faux négatifs.

Ma motivation est simple: étant donné le grand nombre d'éléments à traiter (avec les doublons), nous aimerions éviter de traiter des éléments que nous avons vus auparavant. Cela ne fait pas de mal de traiter une copie, c'est juste une perte de temps. Pourtant, si nous négligions de traiter un élément, ce serait catastrophique. Avec un "filtre Bloom inverse", vous pouvez stocker les éléments vus avec un encombrement réduit, et éviter de traiter les doublons avec une probabilité élevée en testant leur appartenance à l'ensemble.

Pourtant, je n'arrive pas à trouver quoi que ce soit de ce genre. Les filtres les plus proches que j'ai trouvés sont les " filtres de Bloom retouchés ", qui permettent d'échanger des faux positifs sélectionnés contre un taux de faux négatif plus élevé. Je ne sais pas comment leur structure de données fonctionne quand on veut supprimer tous les faux positifs, cependant.

Quelqu'un a vu quelque chose comme ça? :)

Christopher Monsanto
la source
3
Le complément de l'ensemble qui m'intéresse est infini. Comment pourrais-je le stocker?
Christopher Monsanto,
11
Je vois le problème (les disques modernes ne sont pas encore assez gros).
Dave Clarke
8
Si vous disposiez d'une telle structure de données, vous pouvez l'utiliser pour "tricher" en l'utilisant conjointement avec un filtre de bloom régulier et en enregistrant une appartenance exacte à un ensemble.
Mark Reitblatt
1
@MarkReitblatt Les filtres et les caches de Bloom sont probabilistes et toute combinaison de ceux-ci sera probabiliste, c'est-à-dire qu'elle ne sera pas en mesure de réaliser des tests d'adhésion définis. :)
awdz9nld

Réponses:

25

Une solution consiste à utiliser une grande table de hachage et, lorsqu'elle est pleine, commencez à y remplacer des éléments plutôt que de rechercher des emplacements (inexistants) ailleurs pour eux. Vous n'obtenez pas le taux fixe de fausses réponses que vous obtenez avec les filtres de Bloom, mais c'est mieux que rien. Je pense que cela est standard, par exemple dans un logiciel d’échecs pour garder une trace des positions qui ont déjà été recherchées.

David Eppstein
la source
Merci d'avoir répondu. Ouais, c'est la solution évidente - si c'est aussi la solution standard , on dirait que je n'ai pas de chance. Tant pis.
Christopher Monsanto,
2
Cela s'appelle un cache mappé directement et est couramment utilisé dans les processeurs. (Tout cache ou jeu de hachage avec perte convient aux exigences à des degrés divers). Le taux d'erreur est fonction de la distribution de la fonction de hachage (avalanche) et du nombre d'emplacements disponibles dans le cache / ensemble - ajustez en conséquence. :)
awdz9nld
Notez également que seules les clés verbatim peuvent être stockées sans introduire de faux positifs (par exemple, le stockage d'une clé hachée)
awdz9nld
20

La réponse à cette question est "non". Pour voir pourquoi, nous pouvons penser à un cas très extrême et à la manière dont un filtre de bloom ordinaire fonctionnerait par rapport à un filtre de bloom théorique "Bizzaro World", que nous pouvons appeler un "filtre de morosité".

Ce qui est génial avec un filtre bloom, c'est que vous pouvez effectuer des tests unilatéraux d'appartenance d'éléments (avec des faux positifs) à l'aide d'une structure de données de taille fixe en ce qui concerne la probabilité d'erreur et le nombre d'éléments stockés. La taille des articles eux-mêmes n'a pas d'importance. Par exemple, si nous avions un filtre bloom configuré pour stocker jusqu'à 1 000 éléments avec moins de 3% d'erreur, nous pourrions alors stocker 1 000 versions légèrement différentes du corpus entier de Wikipédia, avec une lettre modifiée dans chaque, et nous continuerions de le faire. obtenir les métriques que nous voulons, et la structure de données serait très petite (moins d'un kilo-octet). Bien sûr, le calcul de ces hachages constituera un défi, mais le principe est toujours valable.

Maintenant, envisagez de stocker ces mêmes énormes chaînes dans un filtre de ténèbres! Nous ne pouvons avoir que des faux négatifs maintenant. Donc, si nous disons "oui, cette version de l'ensemble du corpus de Wikipédia est dans cet ensemble", alors nous devons avoir absolument raison à ce sujet. Cela signifie que le hachage ne nous aidera pas, car il y aura toujours une autre chaîne qui hachera à la même valeur. La seule façon de dire «oui» et d’être sûr est de stocker la chaîne entière ou des données équivalentes de la même longueur. Nous pourrions toujours ne pas le stocker et dire «non», mais le taux d'erreur finira par nous rattraper. Le mieux que nous puissions faire est de compresser, en ramenant la taille de la structure au produit de l’entropie des données stockées et de la précision que nous souhaitons.

Donc, malheureusement, le filtre de la morosité n'existe pas. La mise en cache est la seule solution, mais ce n’est pas vraiment le contraire d’un filtre anti-bloom, car sa taille sera proportionnelle au produit de la quantité d’information stockée et du taux de précision souhaité du filtre. Bien sûr, dans de nombreux scénarios réels, les données volumineuses peuvent être représentées par un ID, de sorte que la mise en cache peut encore être tout à fait acceptable. Mais il est fondamentalement différent du puissant filtre bloom.

pents90
la source
caisse somethingsimilar.com/2012/05/21/the-opposite-of-a-bloom-filter - ce qui ne va pas cette mise en œuvre /
Yehosef
@Yehosef c'est bien et cela peut répondre à vos besoins, mais vous remarquerez que l'auteur parle de l'existence de "quelques identifiants identifiant complètement l'événement". Ainsi, ce qui est mis en œuvre est toujours en train de stocker l'objet entier. Donc, c'est une variante d'un cache. Un véritable "opposé d'un filtre de bloom", s'il existait, n'aurait pas besoin de stocker des objets entiers.
pents90
Il a mentionné quelques identifiants qui identifient l'événement - pas l'objet entier. J'ai juste besoin de garder le "cache" sur le session_id - pas l'enregistrement complet d'interaction. Mais j'entends dire que ce n'est pas le même type d'approche que le bloom ou un hyperloglog.
Yehosef
Dans votre "preuve", vous supposez qu'il y a un nombre illimité d'entrées possibles. Cependant, il existe des cas où l’ensemble des entrées possibles est connu à l’avance. Par exemple, pour la récupération de place d'une page mémoire: vous savez quelles entrées elle contient. Vous créez maintenant un "filtre de loup" qui mappe chaque entrée possible sur un index 0..n. Désormais, lorsqu'une entrée est supprimée, définissez le bit sur cet index. Lorsque tous les bits sont définis, vous pouvez ramasser la page. Le "filtre de lueur" est un MPHF. Pour permettre les faux négatifs, modifiez le MPHF de sorte que certaines entrées soient mappées sur n + 1.
Thomas Mueller
@ThomasMueller Oui, je suppose que c'est le cas le plus défavorable / contradictoire, qui correspond au point de vue de la théorie standard de la CS. Il est vrai que si vous avez seulement un ensemble fixe de N entrées possibles, il existe de nombreuses solutions simples, avec uniquement l'espace de log N requis pour chaque élément. Le filtre de bloom n'a pas de telles limitations, cependant.
pents90
13

Vous voulez juste une cache , mais y réfléchissez d'une manière étrange.

Craig Gidney
la source
1
... tu veux élaborer? Bien sûr, un cache fonctionnerait, mais ce n'est pas idéal, d'où une question sur l'état de l'art des structures de données probabilistes. Pour être plus précis, les techniques de mise en cache que je connais nécessitent beaucoup de mémoire. Plus il y a de niveaux de cache, plus la quantité de stockage utilisée est importante. Il est possible de placer une limite sur les éléments stockés dans le cache, de faire des tours avec les modèles d'utilisation, etc., mais cela ne s'approche toujours pas du taux d'efficacité espace / faux réponses fourni par un filtre de Bloom.
Christopher Monsanto,
1
(suite) Cela étant dit, je pourrais oublier une technique de mise en cache évidente qui résout tous mes problèmes. Dans ce cas, vous pourriez expliciter cette technique au lieu de me donner un lien vers une catégorie générale sur Wikipedia?
Christopher Monsanto,
2

CLAUSE DE NON-RESPONSABILITÉ: Je ne suis pas un expert en caches, donc cela pourrait être une idée naïve et peut-être aussi une idée connue dont je n’avais jamais entendu parler auparavant. Alors excusez-moi si je ne cite pas sa référence (si elle existe); et s'il vous plaît, informez-moi s'il existe une référence pour modifier le message et l'ajouter. (Je soupçonne que cela pourrait avoir une référence parce que c'est tellement intuitif).

cc

M. Alaggan
la source
0

J'ai utilisé des arbres AVL (et parfois rouge-noir) avec des éléments partiels pour agir en tant que filtre sans faux négatifs. Utilisez uniquement les X premiers octets de l'élément lors de l'insertion ou de l'interrogation de l'arborescence. Comme la structure de données n’est pas de forme probabiliste, il n’ya pas de risque de collision faux-positif par bit. Et contrairement à la mise en cache de tout l'élément, cette approche vous donne un espace maximum calculable. Vous pouvez ajuster le taux de faux positifs en considérant différentes longueurs de préfixe / profondeurs d'arborescence par rapport au coût des faux positifs et de l'espace.

JRideout
la source
J'ai également voulu essayer des essais avec des données de chaîne, mais mes données ont tendance à être des structures binaires compactées.
JRideout
0

Je pense que l'on peut prouver une limite inférieure indiquant que la structure de données ci-dessus ne peut pas exister. Fondamentalement, si la structure de données utilise m bits, un vecteur de bits fixe (représentation d’une entrée) peut correspondre à au plus (((un)) + n eps) \ choisir (un) ensembles définis par un argument de comptage. Étant donné que 2 ^ m fois, ce nombre doit être au moins égal à u (choisir \ n) (tous les ensembles doivent être représentés), nous obtenons une limite inférieure qui est fondamentalement très proche du stockage précis de l'ensemble S.

Mayank
la source