Filtro Bloom e hash perfeito

7

Um filtro Bloom usa uma função de hash para testar a associação em um determinado conjunto , verificando se um item está presente ou não na posição especificada.S

Para mitigar o efeito da colisão de hash, várias funções são usadas, produzindo um limite probabilístico se o hash universal for usado.

Podemos usar 10 bits por elementos para ter uma taxa de erro 'razoável'.

Se pudéssemos criar diretamente uma função hash perfeita para o conjunto , onde o último elemento não está presente em , poderíamos usar apenas 1 bit por elemento e obter uma recuperação perfeita.S+∞S

Quais são as razões fundamentais pelas quais esse raciocínio está errado?

data-structures hash probabilistic-algorithms bloom-filters dictionaries Nicolas
fonte
11
Qual é o tamanho de e por que 10 bits é "razoável"? S
Pål GD
Por que o tamanho S entra em jogo? Eu posso estar perdendo alguma coisa.
Nicolas # 1
2
Por que você acha que algo está errado com seu raciocínio?
Jeffe
@JeffE Seria estranho encontrar uma enorme economia de espaço quando a qualidade reconhecida do filtro bloom for sua parcimônia. Dito isto, eles contam com funções de hash universais, portanto, isso pode não ser surpreendente. Eu acho que, no caso extremo, a duração do programa necessário para descrever o hash teria um limite de kolmogorov (?) Que limita a eficácia. Da mesma forma, se encontrarmos uma função que tenha "melhorado" isso provavelmente viria provavelmente a algum custo de espaço do programa que compensasse os ganhos. mas eu não sei nada disso, daí a minha pergunta ...
nicolas
2
Seu raciocínio é perfeitamente correto. Você pode obter uma recuperação perfeita usando apenas um bit por elemento com uma função de hash perfeita. A estrutura de dados resultante seria completamente inútil, porque uma função de hash perfeita levaria muito tempo para ser avaliada, mas economizaria muito espaço!
7113 JeffE

Respostas:

7

Eu acho que seu raciocínio está em princípio correto. O hash perfeito é uma alternativa aos filtros Bloom. Entretanto, o hashing perfeito dinâmico clássico é mais um resultado teórico do que uma solução prática. O hash do cuco é provavelmente a alternativa mais "razoável".

Observe que o desempenho do hashing perfeito dinâmico e do hashing cuco padrão é esperado apenas amortizado (talvez seja necessário reconstruir a estrutura de dados completamente de tempos em tempos). Também o filtro Bloom é mais fácil de implementar. Isso pode ser argumentos para usar um filtro Bloom, especialmente se você pode viver com falsos positivos.

A.Schulz
fonte
2

Acho que o filtro Bloom oferece algo que a função hash perfeita não oferece - ele pode testar a associação.

Os PHFs que conheço retornam alguma resposta para qualquer chave à qual você os aplica. Se a chave que você forneceu não estiver no seu conjunto de hash, algum valor ainda será fornecido. Isso é bom se você estiver armazenando todas as teclas que estão no seu conjunto em algum lugar e o PHF fornecer apenas um ponteiro, ou se você estiver usando apenas o PHF para procurar dados de satélite do tamanho nas teclas que encontrar. saber estar em sua estrutura. No entanto, o teste de associação é mais difícil.O(1)

Em particular, armazenar elementos distintos sem erro requer bits de armazenamento.nnlog2⁡n

jbapple
fonte