Combinaison de filtres Bloom

Question

J'utilise des filtres Bloom pour vérifier les données dupliquées dans un ensemble. Cependant, il est nécessaire de combiner les résultats de deux ensembles de données dans un seul filtre pour vérifier la duplication entre les deux ensembles. J'ai conçu une fonction pseudo-Python pour effectuer cette tâche:

def combine(a : bloom_filter, b : bloom_filter): 
    assert a.length == b.length 
    assert a.hashes == b.hashes 

    c = new bloom_filter(length = a.length, hashes = b.hashes) 
    c.attempts = a.attempts + b.attempts 
    c.bits = a.bits | b.bits 

    # Determining the amount of items 
    a_and_b = count(a & b) 
    a_not_b = count(a & !b) 
    not_a_b = count(!a & b) 
    neither = count(!a & !b) 
    c.item_count = a_not_b/a.length * a.item_count 
       + not_a_b/b.length * b.item_count 
       + a_and_b/c.length * min(a.item_count, b.item_count) 

    return c 

Est-ce son même correct? J'ai un débat interne considérable quant à savoir s'il est même possible de faire ce que j'ai l'intention, étant donné qu'une grande partie de l'information sur les données sources est perdue (ce qui est le point d'un filtre bloom).

Answer 1

Vous pouvez obtenir une formule pour estimer la quantité d'articles un filtre Bloom:

c = log(z/N)/((h * log(1 - 1/N)) 

N: Number of bits in the bit vector 
h: Number of hashes 
z: Number of zero bits in the bit vector 

Ceci fournit une estimation assez précise du nombre d'éléments dans le filtre Bloom. Vous pouvez obtenir une estimation pour la contribution avec la soustraction simple.

Answer 2

Il pourrait être possible ..... en quelque sorte ..

permet de dire que l'ensemble A contient des pommes et des oranges

permet de dire que l'ensemble B contient les pois et les carottes

construire simple 16 bits filtre à fleur, par exemple, et comme le hachage CRC32

crc32(apples) = 0x70CCB02F 

crc32(oranges) = 0x45CDF3B4 

crc32(peas) = 0xB18D0C2B 

crc32(carrots) = 0x676A9E28 

Démarrer w/filtre à fleur vide (BF) (par exemple 16 bits) pour les deux ensembles (A, B)

BFA = BFB = 0000 0000 0000 0000 

puis, brisant le hachage dans une certaine longueur de bits, nous utiliserons ici 4 nous pouvons ajouter des pommes à la BF. par exemple.

Get Apples BF Index list by splitting up the hash: 

0x70CCB02F = 0111 0000 1100 1100 1011 0000 0010 1111 
      7  0 C C B  0 2  F  
---------------------------------------------------- 

Add Apples to BFA by setting BF bit indexes [ 7, 0, 12, 12, 11, 0, 2, 15] 

           (set the index bit of an empty BF to 1) 
Apples =  1001 1000 1000 0101 (<- see indexes 0,2,7,11,12,15 are set) 
BF =   0000 0000 0000 0000 (or operation adds that item to the BF) 
================================ 
Updated BFA = 1001 1000 1000 0101 

Ajouter Oranges à BF même:

0x45CDF3B4 = 0100 0101 1100 1101 1111 0011 1011 0100 
       4 5 12 13 15 3 11 4 
---------------------------------------------------- 
Add oranges to BF by setting BF bit indexes [ 4,5,12,13,15,3,11,4] 

Oranges =  1011 1000 0011 1000 
BFA =   1001 1000 1000 0101 (or operation) 
================================ 
Updated BFA = 1011 1000 1011 1101 

Alors maintenant, les pommes et les oranges sont insérés dans BF1 w/valeur finale de 1011 1000 1011 1101

Faites la même chose pour BFB

crc32(peas) = 0xB18D0C2B becomes => 
set [11,2,12,0,13,1,8] in BFB 
0011 1001 0000 0011 = BF(peas) 

crc32(carrots) = 0x676A9E28 becomes => 
set [8,2,14,9,10,6,7] in BFB 

0100 0111 1100 0100 = BF(carrots) 

so BFB = 
0011 1001 0000 0011 BF(peas) 
0100 0111 1100 0100 BF(carrots) 
=================== ('add' them to BFB via locial or op) 
0111 1111 1100 0111 

vous pouvez maintenant rechercher B pour les entrées A dans une boucle et vice versa:

Est-ce que B contient "oranges" =>

1011 1000 0011 1000 (Oranges BF representation) 
0111 1111 1100 0111 (BFB) 
=====================  (and operation) 
0011 1000 0000 0000 

Parce que ce résultat (0011 1000 0000 0000) ne correspond pas à la BF originale d'oranges, vous pouvez être certain que B ne contient pas d'oranges

... (faire pour le reste des articles)

et suivantes, B ne contient aucun des articles A, tout comme B ne contient aucune des pommes.

Je ne pense pas que c'est ce que vous avez demandé si, et ressemble à l'ordinateur que vous pourriez avoir une différence BF, ce qui est plus à votre point. On dirait que vous pourriez faire une séance de XOR et qui vous donnerait un tableau « unique » contenant à la fois des différences:

0111 1111 1100 0111 (BFB) 
1011 1000 1011 1101 (BFA) 
======================== 
1100 0111 0111 1010 (BFA xor BFB) == (items in B not in A, and items in A not in B) 

sens avec ce seul BF, vous pouvez détecter la non-existance d'un article 100% du temps , juste pas l'existance de l'article 100%.

La façon dont vous l'utiliser, est la suivante (vérifier si les pois sont « absents de A):

1100 0111 0111 1010 (BFA xor BFB) 
0011 1001 0000 0011 (Peas) 
============================== (And operation) 
0000 0001 0000 0010 (non-zero) 

depuis (BFA xor BFB) && (Peas) != 0 vous connaissez un jeu ne contient pas « pois » ...

encore, vous seriez tester pour article par article, peut-être vous pourriez faire l'agrégation mais probablement pas une bonne idée ...

Espérons que cela aide!