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. |
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?
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?