Bits & Bytes

Bloom Filter: uma estrutura de dados probabilística que pode te ajudar a economizar (e muito)

Melhorias significativas no desempenho de aplicações acontecem, primeiro, pela revisão da arquitetura. Depois, pela seleção acertada de algoritmos e estruturas de dados. Apenas em casos extremos, micro otimizações fazem sentido. Bloom Filter é uma daquelas estruturas que podem economizar muito dinheiro.
Elemar Júnior
|
18/09/2022

Estou preparando o conteúdo do meu curso de algoritmos e estruturas de dados (que, aliás, está em pré-venda com preço promocional). Dentre os temas que não posso deixar de abordar, sem dúvidas, está a Bloom Filter. 

Trata-se de uma estrutura de dados probabilística, que demanda pouquíssimo espaço, concebida por Burton Howard Bloom em 1970. Ela é utilizada para testar se um elemento faz parte de um conjunto. Eventualmente, testes podem resultar “falsos positivos” (indicando que um elemento está em um conjunto quando, na verdade, não está), mas nunca “falsos negativos”.

A principal motivação para adotar a Bloom Filter é reduzir a quantidade de consultas exaustivas, potencialmente mais caras, em recursos “fonte-da-verdade”.

Considere, por exemplo, que você deseja verificar se um e-mail está presente em um cadastro contatos em uma base de usuários remota com milhares de registros, antes de aceitá-lo em um novo cadastro. O uso de uma bloom filter em client-side pode “aliviar” os servidores.

Pois é, o código mais rápido que existe sempre será aquele que não precisa ser executado. 

O segredo da Bloom Filter é a utilização de hashes de qualidade que são utilizados para ligar ou desligar bits em um mapa. Sempre que um dado é “incluído” no filtro, os bits correspondentes do hash são ligados. Para verificar se um dado está no filtro, basta verificar se todos os bits correspondentes ao hash estão ligados. Caso estejam, o dado poderá estar no conjunto. Caso contrário, o dado certamente não estará (você poderá encontrar uma explicação muito mais aprofundada na Wikipedia ou no meu curso)

Os exemplos para utilização de Bloom Filter são diversos e as economias que ela pode gerar são gigantescas, principalmente em cenários onde escalabilidade é uma necessidade real.

Algorithms and Data Structures for Massive Datasets

Excelentes explicações, detalhadas, sobre a Bloom Filter e outras estruturas de dados sofisticadas podem ser encontradas nesse ótimo livro.

Acessar livro

Há algum tempo, compartilhei uma implementação genérica da Bloom Filter no blog da EximiaCo. Definitivamente, preciso melhorar aquele exemplo.

Conhecia a Bloom Filter? Que outra estrutura de dados quer que eu adicione ao meu curso?

Compartilhe este conteúdo: 

Comentários

Participe deixando seu comentário sobre este artigo a seguir:

Subscribe
Notify of
guest
1 Comentário
Oldest
Newest Most Voted
Inline Feedbacks
View all comments
Diego C. Vigil
Diego C. Vigil
1 ano atrás

O bloom filter é uma estrutura interessante, que conheci a pouco tempo. Vejo alguns exemplos onde são usados até 3 funções hash para se certificar da não existência do item buscado. Quantos você considera ideal e quais os trade offs?

1
0
Quero saber a sua opinião, deixe seu comentáriox
()
x

TRABALHE COMIGO

Sempre tem espaço para gente boa nos projetos em que estou envolvido, então, vai ser um prazer contar com você!

Me fale um pouco sobre a sua trajetória e me deixe saber o que você está buscando. Quero saber também como trabalhar comigo pode fazer diferença para você e como você acha que pode fazer diferença para mim.


DADOS PESSOAIS

SOBRE VOCÊ