Объединение Блум-фильтров - PullRequest
Новая
       19

Объединение Блум-фильтров

3 голосов
/ 23 мая 2011

Я использую фильтры Блума, чтобы проверить наличие дублированных данных в наборе.Однако необходимо объединить результаты двух наборов данных в один фильтр, чтобы проверить наличие дублирования в двух наборах.Я разработал функцию в псевдо-Python для выполнения этой задачи: 

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

Это даже звучит правильно ?У меня ведутся серьезные внутренние споры о том, возможно ли вообще делать то, что я намереваюсь, так как большая часть информации об исходных данных теряется (что является точкой фильтра Блума).

Ответы [ 2 ]

2 голосов
/ 05 июня 2011

Вы можете получить формулу для оценки количества предметов в фильтре Блума: 

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

Это обеспечивает довольно точную оценку количества предметов в фильтре Блума.Вы можете составить оценку вклада с простым вычитанием.

1 голос
/ 16 ноября 2012

Это может быть возможно ..... вроде ..

скажем, набор А содержит яблоки и апельсины

допустим, набор Б содержит горох и морковь

создайте простой 16-битный фильтр Блума в качестве примера и CRC32 в качестве хэша 

crc32(apples) = 0x70CCB02F

crc32(oranges) = 0x45CDF3B4

crc32(peas) = 0xB18D0C2B

crc32(carrots) = 0x676A9E28

Запуск с пустым фильтром Блума (BF) (скажем, 16 бит) для обоих наборов (A, B) 

BFA = BFB = 0000 0000 0000 0000

затем, разбивая хеш на битовую длину, мы будем использовать 4, здесь мы можем добавить яблоки в BF.например, 

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

Добавить апельсины в BF таким же образом: 

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

Так что теперь яблоки и апельсины вставляются в BF1 с окончательным значением 1011 1000 1011 1101

Doто же самое для 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

теперь вы можете искать B для записей A в цикле и наоборот:

Содержит ли B "апельсины" => 

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

Поскольку этот результат (0011 1000 0000 0000) не соответствует оригинальному BF апельсинов, вы можете быть уверены, что B не содержит никаких апельсинов

... ... (сделать для остальных предметов)

и далее, В не содержит ни одного из предметов А, точно так же, как В не содержит яблок.

Я не думаю, что это то, о чем вы спрашивали, и похоже на васможет компьютер разница BF, которая больше к вашей точке.Похоже, что вы могли бы выполнить операцию xor, и это дало бы вам «единственный» массив, содержащий оба различия: 

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)

, то есть с этой единственной BF вы можете обнаружить отсутствие элемента 100% отвремя, а не время существования предмета 100%.

То, как вы его используете, выглядит следующим образом (проверьте, отсутствует ли горох в A): 

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

, так как(BFA xor BFB) && (Peas) != 0 вы знаете, что один набор не содержит 'горох' ​​...

снова, вы будете тестировать по пунктам, возможно, вы могли бы сделать агрегацию, но, вероятно, не очень хорошая идея ...

Надеюсь, это поможет!

...