Na implementação de um filtro Bloom, a abordagem tradicional exige várias funções hash independentes. Kirsch e Mitzenmacher mostraram que você realmente precisa apenas de dois e pode gerar o restante como combinações lineares.
Minha pergunta é: qual é realmente a diferença entre duas funções de hash e uma com o dobro da entropia?
Isso vem da observação do que você realmente faz com a saída de suas funções de hash: você pega seu (digamos) valor de hash de 64 bits e o dimensiona para o tamanho do seu vetor de bits, que provavelmente é significativamente menor que 2 64 . Essa é claramente uma transformação que perde a entropia (exceto nos raros casos, o tamanho do hash e a capacidade do filtro coincidem exatamente). Supondo que meu filtro tenha menos de 2 32 entradas, o que me impede de dividir meu valor de hash de 64 bits em dois hashes de 32 bits e usar combinações lineares deles? Ou usá-lo para propagar um PRNG?
Em outras palavras, quantas informações eu realmente preciso saber sobre cada elemento que insiro em um filtro Bloom para garantir que a taxa de falsos positivos padrão seja mantida? Ou, de maneira mais geral, qual é a relação entre o quão bem eu posso distinguir elementos (quantos bits eu uso para descrevê-los) e o desempenho do meu filtro Bloom?
Parece que posso obter bits para um tamanho de filtro de m ou equivalentemente 2 ( lg ( - n ln p ) - 2 lg ( ln 2 ) ) bits para armazenar n elementos com probabilidade de falso positivo ....