Un ensemble probabiliste sans faux positifs?

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? :)

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.

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.

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

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).

$c$$c$

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.

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.