Вычисление приблизительной популяции фильтра Блума

12

Дан фильтр Блума размером N битов и K хэш-функций, из которых установлены M-биты (где M <= N) фильтра.

Можно ли приблизить количество элементов, вставленных в фильтр Блума?

Простой пример

Я обдумывал следующий пример, предполагая, что BF состоит из 100 битов и 5 хэш-функций, где установлены 10 битов ...

В лучшем случае: если предположить, что хеш-функции действительно идеальны и однозначно отображают бит для некоторого числа значений Х, то, учитывая, что 10-битные значения установлены, мы можем сказать, что в BF было вставлено только 2 элемента.

В худшем случае: если предположить, что хэш-функции плохие и постоянно отображаются в один и тот же бит (но уникальны друг для друга), то можно сказать, что в BF было вставлено 10 элементов.

Похоже, что диапазон [2,10], где значение about в этом диапазоне, вероятно, определяется ложноположительной вероятностью фильтра - я застрял в этой точке.

Тандер Кулип
источник
4
Почему бы не сохранить счетчик количества вставленных элементов? Это займет только дополнительные бит, если вы вставили n элементов. O(logn)n
Джо
@ Джо, хотя это хорошая идея, она испортила действительно интересный вопрос.
dan_waterworth
Просто отметив, что с дубликатами у метода Джо будет небольшая ошибка, так как мы не всегда можем точно сказать, добавляя элемент, присутствует ли он уже (и, следовательно, следует ли увеличивать счет или нет).
усуль

Ответы:

5

Да. Из Википедии :

Если вы вставили элементы в фильтр размера n с использованием k хеш-функций, вероятность того, что определенный бит по-прежнему равен 0, равнаink

z=(11n)ki

Вы можете измерить эту вероятность как пропорцию 0 бит в вашем фильтре. Решение для даетi

i=ln(z)kln(11n)

Я использовал это на практике, и пока ваш фильтр не превышает его емкость, ошибка обычно составляет менее 0,1% для фильтров до миллионов битов. Поскольку фильтр превышает его емкость, ошибка, конечно, возрастает.

Джей Хакер
источник
3

Если вы предполагаете, что для каждой хэш-функции для каждого объекта бит задан равномерно случайным образом, и у вас есть счетчик количества установленных битов, вы должны иметь возможность ограничить вероятность того, что количество вставленных объектов было в определенном диапазоне, возможно, с использованием формулировки шаров и бункеров. Каждый бит является ячейкой, и он устанавливается, если в нем есть хотя бы 1 шарик, каждый вставленный объект бросает шариков, где k - количество хеш-функций, а n k - количество шариков, брошенных после вставки n объектов. , Учитывая , что б бункеров, по крайней мере , 1 мяч в них, что вероятность того, что по крайней мере , т шары были брошены? Я думаю, что здесь вы можете использовать тот факт, что: kknknbt Но проблема с такой формулировкой состоит в том, что я не вижу простого способа вычислить P ( t ) или P ( b ) , но найти значение t, которое максимизирует эту вероятность, не должно быть слишком сложно.

P(t balls|b bins)=P(b bins|t balls)P(t)/P(b)
P(t)P(b)t
Джо
источник
2

Интересный вопрос, давайте рассмотрим некоторые конкретные случаи.

Пусть ключи, п о п биты, п т о т а л биты в полных и м элементов , вставленных. Сначала мы будем пытаться найти функцию P ( K , п О п , п т о т л , м ) , которая является вероятностью состояние , наступающее.knonntotalmP(k,non,ntotal,m)

Если , то Р ( к , п о п , п т о т л , м ) должен быть 0 , то есть , это невозможно.km<nonP(k,non,ntotal,m)0

Если , то мы ищем вероятность того, что k m хэшей попадут в одно и то же ведро, и первое может пометить, куда должны идти другие. Итак, мы хотим найти вероятность того, что k m - 1 хэшей попадет в конкретный сегмент.non=1kmkm1

P(k,1,ntotal,m)=(1/ntotal)(km1)

Это действительно простые случаи закончились. Если то мы хотим найти вероятность того, что k m хэшей попадет в 2 разных сегмента, и по крайней мере 1 попадет в каждое. Есть п т о т л ( н т о т л - 1 ) пара ведер и вероятность того , что хеши земли в каком - либо конкретной 2 является ( 2 / п т о т л ) к мnon=2km21ntotal(ntotal1)2(2/ntotal)kmтаким образом, вероятность того, что хэши попадут в блока, равна:2

ntotal(ntotal1)(2/ntotal)km

Мы уже знаем вероятность того, что они упадут в ведро, поэтому давайте вычтем это, чтобы дать вероятность того, что они упадут ровно в 2 .12

P(k,2,ntotal,m)=ntotal(ntotal1)(2/ntotal)km(1/ntotal)(km1)

Я думаю, что мы можем обобщить это сейчас.

P(k,non,ntotal,m)=(ntotalnon)(non/ntotal)kmi=1i<nonP(k,i,ntotal,m)

Я не совсем уверен, как сделать эту формулу более поддающейся вычислению. Наивно реализованный, он привел бы к экспоненциальному времени выполнения, хотя с помощью запоминания тривиально добиться линейного времени. Тогда это всего лишь случай нахождения наиболее вероятного . Мой инстинкт говорит, что будет один пик, так что может быть возможно найти его очень быстро, но наивно, вы определенно можете найти наиболее вероятный m в O ( n 2 ) .mO(n2)

dan_waterworth
источник
Я думаю , что ваша формула сокращается до (без учета постоянных факторов). Вы можете вычислить максимум этого аналитически: расширить первый множитель второго члена и удалить постоянные факторы, чтобы избавиться от всего, и тогда ваша формула станет очень простой. (ntotalnon)nonkm(ntotalnon1)(non1)kmn choose k
Жюль
@ Джулс, отлично, я был уверен, что что-то подобное случится, но у меня не было времени это выяснить.
dan_waterworth
P(non=x)=P(nonx)P(non<x)=P(nonx)P(nonx1)(ntotalx)(x/ntotal)kmP(nonx)
2

Предположим, что хэши распределены равномерно.

iimi1mmni1m1n(m1)

P(m,i)=P(m,i1)(m/n)+P(m1,i1)(n(m1))/n

Переписывание:

P(m,i)=1n(mP(m,i1)+(nm+1)P(m1,i1))

P(0,0)=1P(m,0)=0m0P(0,i)=0i0O(mi)iP(m,i) дает вам максимальную оценку вероятности.

iki/k

1nP(m,i)O(nm)iO(jm)jPO(mlogn)

Жюль
источник
2

Ключевой идеей является приблизительное ожидание числа нулевого бита.

(11N)KteKtN

Тогда ожидание нулевых битовых чисел должно быть:

NeKtNNM

t=NKln(1MN)

Янгхонг Чжун
источник
1

Вероятность того, что конкретный бит равен 1 после n вставок, равна: P = 1 - (1 - 1 / m) ^ (kn)

Пусть X_i - дискретная случайная величина, равная 1, если бит в i-й позиции равен 1, а в противном случае - 0. Пусть X = X_1 + X_2 + .... + X_m. Тогда E [X] = m * P.

Если общее число установленных битов равно S, то: E [X] = S, что подразумевает m * P = S. Это можно решить для n.

Нихилу
источник