블룸 필터의 대략적인 모집단 계산 된 요소

크기 N 비트의 블룸 필터와 필터의 M 비트 (여기서 M <= N)가 설정된 K 해시 함수가 제공됩니다.

블룸 필터에 삽입 된 요소 수를 근사 할 수 있습니까?

간단한 예

100 비트의 BF와 10 비트가 설정된 5 개의 해시 함수를 가정하고 다음 예제를 숙고했습니다 …

모범 사례 시나리오 : 해시 함수가 완벽하고 일부 X 값의 비트를 고유하게 매핑한다고 가정하면 10 비트가 설정되면 BF에 2 개의 요소 만 삽입되었다고 말할 수 있습니다

최악의 시나리오 : 해시 함수가 나쁘고 일관되게 동일한 비트에 서로 매핑되어 있다고 가정하면 10 개의 요소가 BF에 삽입되었다고 말할 수 있습니다.

범위는 [2,10]으로 보이며이 범위의 정보는 필터의 오 탐지 확률에 의해 결정됩니다.이 시점에서 멈춰 있습니다.



답변

예. 에서 위키 백과 :

해시 함수를 사용하여 크기 의 필터에 요소를 삽입 한 경우 특정 비트가 여전히 0 일 확률은N K

i

n

k

z=(1−1n)ki

이 확률을 필터에서 0 비트의 비율로 측정 할 수 있습니다 . 주는 해결

i

i=ln⁡(z)kln⁡(1−1n)

실제로 이것을 사용했으며 필터가 용량을 초과하지 않는 한 오류는 일반적으로 수백만 비트까지의 필터에 대해 0.1 % 미만입니다. 필터가 용량을 초과하면 물론 오류가 발생합니다.


답변

각 객체에 대한 각 해시 함수에 대해 비트가 무작위로 균일하게 설정되고 설정된 비트 수를 세는 경우 삽입 된 객체 수가 특정 범위 내에서, 아마도 공 및 통 제형을 사용하는 것. 각 비트는 빈 (bin)이며, 최소 1 개의 볼이있는 경우 설정되며, 삽입 된 각 오브젝트는 볼을 던지며 , 여기서 는 해시 함수의 수이고, 는 오브젝트가 삽입 된 후 발생한 볼의 수입니다 . 빈에 적어도 1 개의 공이 있다고 가정하면 , 적어도 개의 공이 던져 질 확률은 얼마입니까? 나는 여기서 당신이 다음과 같은 사실을 사용할 수 있다고 생각합니다.
k n k n b t P ( t  공 | b  빈 ) = P ( b  빈 | t  공 ) P ( t ) / P ( b ) P ( t ) P ( b ) t

k

k

nk

n

b

t

P(t balls|b bins)=P(b bins|t balls)⋅P(t)/P(b)


그러나 그 공식의 문제 또는 를 계산하는 간단한 방법 은 보이지 않지만 확률을 극대화하는 값을 찾는 것이 너무 어렵지 않아야한다는 것입니다.

P(t)

P(b)

t


답변

흥미로운 질문은 몇 가지 구체적인 사례를 살펴 보겠습니다.

있으라 키 에 비트 합계와 비트 삽입 소자. 먼저 상태가 발생할 확률 인 함수 를 찾으려고합니다 .

k

non

ntotal

m

P(k,non,ntotal,m)

경우 다음 이어야 , 즉 그것은 불가능이다.

km<non

P(k,non,ntotal,m)

0

경우 , 우리는 확률을 찾고 다른 사람들은 어디로 가야 해시가 같은 양동이에 떨어지는, 처음은 표시 할 수 있습니다. 따라서 해시가 특정 버킷에 포함될 확률을 찾고 싶습니다 .

non=1

km

km−1

P(k,1,ntotal,m)=(1/ntotal)(km−1)

그것은 정말 간단한 경우입니다. 경우 우리는 확률을 찾으려면 해시에 땅 별개의 버킷 적어도 각에 빠진다. 버킷 에는 쌍이 있으며 특정 에 해시가 도달 할 확률 은 이므로 해시가 떨어질 확률 에 버킷입니다 :

non=2

km

2

1

ntotal(ntotal−1)

2

(2/ntotal)km

2

ntotal(ntotal−1)(2/ntotal)km

우리는 이미 버킷에 떨어질 확률을 알고 있으므로 정확히 빠질 확률을 뺍니다 .2

1

2

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

지금 일반화 할 수 있다고 생각합니다.

P(k,non,ntotal,m)=(ntotalnon)(non/ntotal)km−∑i=1i<nonP(k,i,ntotal,m)

이 수식을 계산하기에 더 잘 만드는 방법을 정확히 모르겠습니다. 순진하게 구현하면 선형 시간을 달성하기 위해 메모를 통해 사소한 것이지만 지수 시간 실행 시간이 발생합니다. 그런 다음 가장 가능성이 높은 을 찾는 경우입니다 . 내 본능에 따르면 단일 피크가 있으므로 매우 빨리 찾을 수 있지만 순진하게도 에서 가장 가능성이 높은 m을 찾을 수 있습니다 .

m

O(n2)

답변

해시가 균일하게 분산되어 있다고 가정합니다.

하자 삽입 해시의 숫자. 우리가 이후 에 해시 빈들 우리는이 경우 에 해시 빈들, 다음 해시 그 중 하나로 진행 에서 빈들 OR 우리가있는 경우 에 해시를 빈과 다음 해시 간다 다른 빈 중 하나에 다음 이 있습니다.

i

i

m

i−1

m

m

n

i−1

m−1

n−(m−1)

P(m,i)=P(m,i−1)(m/n)+P(m−1,i−1)(n−(m−1))/n

재 작성 :

P(m,i)=1n(mP(m,i−1)+(n−m+1)P(m−1,i−1))

우리는 또한이 및 때 및 경우 . 이는 P를 계산하기위한 동적 프로그래밍 알고리즘을 제공합니다. 를 최대화 하는 를 계산 하면 최대 가능성 추정치가 제공됩니다.

P(0,0)=1

P(m,0)=0

m≠0

P(0,i)=0

i≠0

O(mi)

i

P(m,i)

이 블룸 필터에 번 해시하고 항목 당 해시가있는 경우 항목 수는 입니다.

i

k

i/k

속도를 높이려면 몇 가지 작업을 수행 할 수 있습니다. 요소 는 최대 위치를 변경하지 않으므로 생략 할 수 있습니다. 를 여러 번 호출하여 동적 프로그래밍 테이블을 공유하여 (점근) 실행 시간을 로 줄일 수 있습니다. 단일 최대 값이 있다고 생각한다면 통해 반복을 일찍 중단하고 실행 시간을 얻을 수 있습니다 여기서 는 가 최대 값을 차지하는 지점 이거나 이진 검색을 수행하고 얻습니다. . P(m,i)O(nm)iO(jm)jPO(mlogn)

1n

P(m,i)

O(nm)

i

O(jm)

j

P

O(mlog⁡n)

답변

핵심 아이디어는 제로 비트 수에 대한 기대치를 근사화하는 것입니다.

비트마다, K 해시 함수 t 삽입 후에 제로가되는 가능성은 : .

(1−1N)Kt≈e−KtN

그런 다음 0 비트 숫자의 기대 값은 다음과 같아야합니다.

N-M

Ne−KtN

관측치에 의해 근사 된

N−M

마지막으로

t=−NKln(1−MN)

답변

n 삽입 후 특정 비트가 1 일 확률은 다음과 같습니다. P = 1-(1-1 / m) ^ (kn)

X_i는 i 번째 위치의 비트가 1이면 1이고, 그렇지 않으면 0 인 이산 랜덤 변수입니다. X = X_1 + X_2 + .... + X_m으로 둡니다. 그런 다음 E [X] = m * P.

세트 비트의 총 개수가 S이면, E [X] = S는 m * P = S를 의미한다. 이것은 n에 대해 해결 될 수있다.