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

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

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

간단한 예

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

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

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

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

답변

예. 에서 위키 백과 :

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

$n$

$k$

z = (1 - 1 n) k i

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

i = ln ( z ) k ln ( 1 - 1 n )

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

답변

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

$k$

$n k$

$n$

$b$

$t$

P (t balls | b bins) = P (b bins | t balls) \cdot P (t) / P (b)

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

P(t)

$P (b)$

P(b)

$t$

답변

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

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

$n_{o n}$

non

$n_{t o t a l}$

ntotal

$m$

$P (k, n_{o n}, n_{t o t a l}, m)$

P(k,non,ntotal,m)

경우 다음 이어야 , 즉 그것은 불가능이다. $k m < n_{o n}$

km<non

$P (k, n_{o n}, n_{t o t a l}, m)$

P(k,non,ntotal,m)

$0$

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

non=1

$k m$

$k m - 1$

km−1

$P (k, 1, n_{t o t a l}, m) = (1 / n_{t o t a l})^{(k m - 1)}$

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

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

non=2

$k m$

$2$

$1$

$n_{t o t a l} (n_{t o t a l} - 1)$

ntotal(ntotal−1)

$2$

$(2 / n_{t o t a l})^{k m}$

(2/ntotal)km

$2$

$n_{t o t a l} (n_{t o t a l} - 1) (2 / n_{t o t a l})^{k m}$

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

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

$2$

$P (k, 2, n_{t o t a l}, m) = n_{t o t a l} (n_{t o t a l} - 1) (2 / n_{t o t a l})^{k m} - (1 / n_{t o t a l})^{(k m - 1)}$

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

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

$P (k, n_{o n}, n_{t o t a l}, m) = (\binom{n_{t o t a l}}{n_{o n}}) (n_{o n} / n_{t o t a l})^{k m} - \sum_{i = 1}^{i < n_{o n}} P (k, i, n_{t o t a l}, m)$

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

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

$O (n^{2})$

O(n2)

답변

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

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

$i$

$m$

$i - 1$

i−1

$m$

$n$

$i - 1$

i−1

$m - 1$

m−1

$n - (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)=P(m,i−1)(m/n)+P(m−1,i−1)(n−(m−1))/n

재 작성 :

$P (m, i) = \frac{1}{n} (m P (m, i - 1) + (n - m + 1) P (m - 1, i - 1))$

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

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

P(0,0)=1

$P (m, 0) = 0$

P(m,0)=0

$m \neq 0$

m≠0

$P (0, i) = 0$

P(0,i)=0

$i \neq 0$

i≠0

$O (m i)$

O(mi)

$i$

$P (m, i)$

P(m,i)

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

$k$

$i / k$

i/k

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

$P (m, i)$

P(m,i)

$O (n m)$

O(nm)

$i$

$O (j m)$

O(jm)

$j$

$P$

$O (m \log n)$

O(mlog⁡n)

답변

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

비트마다, K 해시 함수 t 삽입 후에 제로가되는 가능성은 : . $(1 - \frac{1}{N})^{K t} \approx e^{- \frac{K t}{N}}$

(1−1N)Kt≈e−KtN

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

$N e^{- \frac{K t}{N}}$

Ne−KtN

관측치에 의해 근사 된 $N - M$

N−M

마지막으로 $t = - \frac{N}{K} l n (1 - \frac{M}{N})$

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에 대해 해결 될 수있다.

답변

Exit mobile version

How IT

언제든지 물어보세요.

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

답변

답변

답변

답변

답변

답변

답변