Computando a população aproximada de um filtro bloom

12

Dado um filtro de bloom de tamanho N-bits e K funções hash, dos quais M-bits (onde M <= N) do filtro estão definidos.

É possível aproximar o número de elementos inseridos no filtro de bloom?

Exemplo Simples

Eu estive refletindo sobre o exemplo a seguir, assumindo um BF de 100 bits e 5 funções de hash em que 10 bits são definidos ...

Na melhor das hipóteses: supondo que as funções de hash sejam realmente perfeitas e mapeie um pouco de forma exclusiva um número X de valores, então, com 10 bits definidos, podemos dizer que houve apenas 2 elementos inseridos no BF

No pior cenário: supondo que as funções de hash sejam ruins e sejam mapeadas consistentemente para o mesmo bit (ainda que únicas entre si), podemos dizer que 10 elementos foram inseridos no BF

O intervalo parece ser [2,10] onde abouts nesse intervalo provavelmente são determinados pela probabilidade de filtro falso-positivo - estou preso neste momento.

Tander Kulip
fonte
4
Por que não manter um contador do número de elementos inseridos? Leva apenas um adicional bits, se você inseriu n elementos. O(logn)n
31312 Joe
@ Joe, embora essa seja uma boa ideia, ela arruina uma pergunta realmente interessante.
21412 dan_waterworth
Apenas observando que, com duplicatas, o método de Joe terá um pequeno erro, pois nem sempre podemos ter certeza ao adicionar um elemento se ele já está presente (e, portanto, devemos incrementar a contagem ou não).
usul

Respostas:

5

Sim. Da Wikipedia :

Se você inseriu elementos em um filtro de tamanho n usando as funções k hash, a probabilidade de um certo bit ainda ser 0 éink

z=(11n)ki

Você pode medir essa probabilidade como a proporção de 0 bits no seu filtro. Resolução para i

i=ln(z)kln(11n)

Eu usei isso na prática e, desde que seu filtro não exceda sua capacidade, o erro geralmente é menor que 0,1% para filtros de até milhões de bits. Como o filtro excede sua capacidade, é claro que o erro aumenta.

Jay Hacker
fonte
3

Se você presumir que, para cada função de hash de cada objeto, um bit é definido uniformemente aleatoriamente e você conta o número de bits que foram configurados, deve poder limitar a probabilidade de que o número de objetos inseridos seja dentro de um certo intervalo, talvez usando uma formulação de bolas e caixas. Cada bit é uma lixeira e é definido se tiver pelo menos 1 bola, cada objeto inserido lança balls, onde k é o número de funções de hash e n k é o número de bolas lançadas depois que n objetos foram inseridos . Dado que b caixas de ter pelo menos 1 bola em si, qual é a probabilidade de que pelo menos t bolas foram jogadas? Eu acho que aqui você pode usar o fato de que: kknknbt Mas o problema com que a formulação é que eu não vejo uma maneira simples para calcular P ( t ) ou P ( b ) , mas encontrar o valor de t que maximiza essa probabilidade não deve ser muito difícil.

P(t balls|b bins)=P(b bins|t balls)P(t)/P(b)
P(t)P(b)t
Joe
fonte
2

Pergunta interessante, vamos olhar para alguns casos específicos.

knonntotalmP(k,non,ntotal,m)

km<nonP(k,non,ntotal,m)0

non=1kmkm1

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

non=2km21ntotal(ntotal1)2(2/ntotal)km2

ntotal(ntotal1)(2/ntotal)km

12

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

Eu acho que podemos generalizar isso agora.

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

Não sei exatamente como tornar essa fórmula mais passível de computação. Implementado ingenuamente, resultaria em tempo de execução de tempo exponencial, embora seja trivial, via memorização, atingir tempo linear. É então apenas um caso de encontrar o mais provável . Meu instinto diz que haverá um pico único; portanto, é possível encontrá-lo muito rapidamente, mas, ingenuamente, é possível encontrar definitivamente o m mais provavelmente em .mO(n2)

dan_waterworth
fonte
Eu acho que sua fórmula cancela para (ignorando fatores constantes). Você pode calcular o máximo disso analiticamente: expanda o primeiro fator do segundo termo e remova fatores constantes para se livrar de todos , e então sua fórmula se torna muito simples. (ntotalnon)nonkm(ntotalnon1)(non1)kmn choose k
Jules
@Jules, ótimo, eu tinha certeza de que algo assim iria acontecer, mas não tive tempo para descobrir.
21412 dan_waterworth
Você também pode chegar a essa fórmula diretamente da seguinte maneira: . Em seguida, para . P(non=x)=P(nonx)P(non<x)=P(nonx)P(nonx1)(ntotalx)(x/ntotal)kmP(nonx)
Jules
2

Suponha que os hashes sejam distribuídos uniformemente.

Deixe ser o número de hashes inseridos. Como temos hashes em escaninhos se tivermos hashes em escaninhos e o próximo hash entra em um desses de escaninhos OU se temos hashes em escaninhos e o próximo hash vai em um dos outros compartimentos, temos:iimi1mmni1m1n(m1)

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

Reescrever:

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

Também temos e quando e quando . Isso fornece um algoritmo de programação dinâmica para calcular P. O cálculo de que maximiza fornece a estimativa de probabilidade máxima.P(0,0)=1P(m,0)=0m0P(0,i)=0i0O(mi)iP(m,i)

Se soubermos que inserimos esse filtro de bloom vezes e temos hashes por item, o número de itens é .iki/k

Para acelerar, você pode fazer algumas coisas. O fator pode ser deixado de fora, pois não altera a posição do máximo. Você pode compartilhar as tabelas de programação dinâmica com várias chamadas para para reduzir o tempo de execução (assintótico) para . Se você está disposto a acreditar que há um único máximo, você pode parar a iteração sobre cedo e obter tempo de execução onde é o ponto em que assume o seu máximo, ou até mesmo fazer uma busca binária e obter . P(m,i)O(nm)iO(jm)jPO(mlogn)1nP(m,i)O(nm)iO(jm)jPO(mlogn)

Jules
fonte
2

A idéia principal é aproximar a expectativa do número de zero bits.

Para cada bit, a possibilidade de ser zero após t inserções com funções K hash é: .(11N)KteKtN

A expectativa de números de zero bits deve ser:

N-MNeKtN aproximado pela observaçãoNM

Finalmente, obtivemost=NKln(1MN)

Yanghong Zhong
fonte
1

A probabilidade de um bit específico ser 1 após n inserções é: P = 1 - (1 - 1 / m) ^ (kn)

Seja X_i uma variável aleatória discreta que seja 1 se o bit na i-ésima posição for 1 e 0 caso contrário. Seja X = X_1 + X_2 + .... + X_m. Então, E [X] = m * P.

Se o número total de bits definidos for S, então: E [X] = S, o que implica m * P = S. Isso pode ser resolvido para n.

Nikhil
fonte