O filtro de Bloom trocou algumas respostas erradas por um consumo de memória minúsculo

Quando um conjunto de itens é enorme, armazenar cada chave é impossível, mas ainda é preciso saber se algo está nele. O exemplo de Bloom era um dicionário de 500.000 palavras em que apenas 10% das palavras usam regras caras de hifenização: a verificação sensata era evitar um acesso ao disco, mas o dicionário era grande demais para um hashing sem erros na memória disponível.

Um filtro de Bloom resolve isso com um arranjo de bits e várias funções de hash. Adicionar um item define os bits nessas posições, e o teste pergunta se todos eles estão definidos. Se algum for zero, o item está definitivamente ausente, portanto não há falsos negativos; se todos estiverem definidos, o item pode estar no conjunto ou pode simplesmente ter colidido com outros itens, produzindo um falso positivo.

Como o erro é unilateral e ajustável, a estrutura permanece pequena enquanto ainda elimina a maioria das leituras desnecessárias no disco. Uma área de hash de apenas 18% do tamanho que um hash sem erros precisaria eliminou 87% dos acessos ao disco, e menos de dez bits por elemento dão cerca de 1% de taxa de falsos positivos.

Deixe um arranjo de bits dizer "talvez", nunca "não" por engano

Falsos positivos são aceitáveis quando o custo é apenas uma verificação extra, mas um falso "não" perderia dados.

Um arranjo de bits com algumas funções de hash armazena a pertinência em poucos bits por elemento.

Ele elimina a maioria das consultas caras ao disco ou à rede sem armazenar o conjunto real.

Se uma pequena chance de dizer sim é aceitável, mas um falso não não é, aceite deliberadamente o erro unilateral; permitir alguns falsos positivos costuma ser a única forma de encaixar um conjunto enorme na memória.

Os filtros de Bloom se espalharam por bancos de dados, caches, corretores ortográficos e roteamento de rede para evitar consultas caras, e aparecem em sistemas desde PostgreSQL e Apache Cassandra até Chromium e cache em larga escala; o truque subjacente de aceitar erro unilateral em troca de espaço é hoje uma primitiva padrão em sistemas computacionais.