Filtros de Bloom

Aspectos positivos

Os filtros de Bloom garantem não existência de falsos negativos e usam uma quantidade de memória limitada

• Ótimo para pré-processamento antes de processos mais exigentes

Adequados para implementação em hardware

• As funções de dispersão podem ser paralelizadas

Limitações

Como a tabela não pode ser expandida, o máximo número de elementos a armazenar no filtro tem de ser conhecido previamente

Assim que se excede a capacidade para a qual foi projetado, os falsos positivos aumentam rapidamente ao serem inseridos mais elementos

Compromissos

Os falsos positivos podem ser diminuídos através de:

• Aumento do número de funções de dispersão (até ao K_ó𝑡𝑖𝑚𝑜)

• E do espaço alocado para armazenar o vetor

Comentários finais

Os filtros de Bloom devem ser considerados para programas em que um teste de pertença imperfeito pode ser aplicado a um conjunto de dados (muito) grande

As grandes vantagens de um filtro de Bloom são a rapidez e taxa de erro

Apesar de poder ser aplicado a conjuntos de qualquer dimensão, árvores e heaps são melhores soluções para conjuntos pequenos