Efeito de k na Pfp

Falsos Positivos

Adicionando mais funções não diminui obrigatoriamente essa probabilidade

Decresce até um certo valor de k

Depois aumenta, porquê ?

Redução de falso positivos

FP podem ser reduzidos aumentando o tamanho do vetor B

• neste caso à custa de mais memória

• o efeito da relação n/m é ilustrado na figura

Também podem ser reduzidos aumentando o número de funções de dispersão

• mas apenas até certo valor

Valor ótimo de k

É possível determinar o número de funções de dispersão que minimiza a probabilidade de falsos positivos

Para facilitar os cálculos minimiza-se ln(Pfp)

Aplicando ln() a Ppf = ( 1 - a^k )^k

temos ln(Ppf) = k * ln( 1 - a^k )

Minimização

Derivando, em ordem a k e igualando a zero

• (1 - a^k) * ln(1 - a^k) - a^k * ln(a^k) = 0

Que tem por solução

• a^k = 1/2

k ótimo

O valor ótimo de k pode ser obtido aplicando logaritmos e resolvendo em ordem a k:

• K_ótimo = ln(1/2) / ln(a)

Substituindo o valor de a temos

• K_ótimo = ln(1/2) / ( m * ln( 1 - 1/n ) )

Aproximando ln(1 − 1/n) pelo primeiro termo da série de Taylor (−1/n)

• K_ótimo ~= ( n * ln(2) ) / m

Na prática utiliza-se o inteiro mais próximo