Entendendo o filtro de Bloom com exemplos

 (llimllib.github.io)
2 pontos por GN⁺ 2025-07-01 | 1 comentários | Compartilhar no WhatsApp
  • Filtro de Bloom é uma estrutura de dados que filtra rapidamente a presença de elementos em um conjunto grande usando pouca memória, distinguindo apenas entre “com certeza não está” e “pode estar”
  • O núcleo está no vetor de bits e em várias funções hash; na inserção, os bits apontados pelos resultados dos hashes são definidos como 1
  • Na consulta, se qualquer uma dessas posições for 0, o elemento pode ser descartado, mas mesmo que todas sejam 1 ainda existe a possibilidade de falso positivo
  • As funções hash devem ser independentes, ter distribuição próxima do uniforme e ser rápidas; houve caso de cerca de 800% de ganho de velocidade ao trocar md5 por murmur
  • A precisão e o custo do filtro dependem do equilíbrio entre o número esperado de elementos n, a quantidade de bits m e o número de hashes k; tanto inserção quanto consulta ficam em torno de O(k)

Como o filtro de Bloom funciona

  • Filtro de Bloom é uma estrutura de dados probabilística para verificar de forma rápida e eficiente em memória se um elemento pertence a um conjunto
  • O resultado fica restrito a duas possibilidades
    • o elemento com certeza não está no conjunto
    • o elemento pode estar no conjunto
  • A estrutura interna é um vetor de bits e, ao adicionar um elemento, a entrada passa por várias funções hash
  • Os bits apontados pelos índices gerados pelos hashes são definidos como 1, concluindo a inserção
  • No exemplo, Fnv e Murmur são usados como funções hash simples

Verificação de pertencimento e falsos positivos

  • A consulta também usa as mesmas funções hash da inserção
  • Se qualquer um dos bits apontados pelos hashes for 0, esse elemento com certeza não está no conjunto
  • Se todos os bits relacionados forem 1, o elemento pode estar no conjunto
    • esses mesmos bits podem já ter sido definidos por outro elemento ou por uma combinação de vários elementos
  • Por causa dessas colisões, o filtro de Bloom tem possibilidade de falso positivo (false positive)

Critérios para escolher funções hash

  • As funções hash de um filtro de Bloom devem ser independentes, ter distribuição próxima do uniforme e ser tão rápidas quanto possível
  • Hashes criptográficos como sha1 são amplamente usados, mas nem sempre são uma boa escolha para filtros de Bloom
  • Exemplos de hashes rápidos e simples:
  • Há um caso em que uma implementação de filtro de Bloom obteve cerca de 800% de ganho de velocidade após trocar md5 por murmur

Hashes usados em implementações reais

  • Várias implementações usam funções hash diferentes em seus filtros de Bloom

Definindo o tamanho do filtro e a quantidade de funções hash

  • O filtro de Bloom permite ajustar a taxa de falsos positivos
    • um filtro maior reduz os falsos positivos
    • um filtro menor aumenta os falsos positivos
  • A taxa de falso positivo pode ser calculada aproximadamente por (1-e^-kn/m)^k
    • n: número esperado de elementos a serem inseridos
    • m: número de bits do filtro
    • k: número de funções hash
  • Quanto mais funções hash houver, mais lentas ficam as consultas e inserções, e mais rápido o filtro se enche
  • Por outro lado, se houver poucas funções hash, a quantidade de falsos positivos pode ficar excessiva
  • Para valores dados de m e n, o valor ótimo de k pode ser escolhido como (m/n)ln(2)
  • O tamanho do filtro pode ser ajustado na seguinte ordem
    • estimar aproximadamente o valor de n
    • escolher o valor de m
    • calcular o valor ótimo de k
    • calcular a taxa de erro com os valores escolhidos de n, m e k
    • se a taxa de erro não for aceitável, alterar m e calcular novamente

Desempenho e condições adequadas de uso

  • Em um filtro de Bloom com m bits e k funções hash, tanto a inserção quanto a verificação de pertencimento são O(k)
  • Ao adicionar ou consultar um elemento, basta passá-lo por k funções hash e então definir ou verificar os bits correspondentes
  • A eficiência de espaço varia conforme a taxa de erro aceitável
  • Se o intervalo de elementos que podem ser inseridos for muito limitado, um vetor de bits determinístico pode ser melhor
  • Se não for possível estimar nem aproximadamente quantos elementos serão inseridos, uma tabela hash ou um scalable Bloom filter pode ser mais apropriado

Materiais de referência e exemplos de uso

Leituras relacionadas

1 comentários

 
GN⁺ 2025-07-01
Opiniões no Hacker News

  • Este texto foi feito exatamente para pessoas como eu. Eu já tinha ouvido o nome filtro de Bloom e, toda vez que ele era mencionado, só pensava que precisava pesquisar sobre isso. Ao ver este texto, finalmente fui atrás, e ele foi perfeito como a introdução que eu queria :)

    • Conheci filtros de Bloom há mais de 10 anos, quando recebi a tarefa de implementá-los para a função de busca do iBooks
    • É uma estrutura realmente interessante. Quando aparece um problema que precisa de um filtro de Bloom, fico animado; infelizmente, dependendo da área, esses casos podem ser raros

  • Em 2009, na faculdade, criei um filtro de Bloom em CUDA, e meu orientador tinha vindo da Nvidia. Mas depois disso acabei não fazendo nenhuma programação em GPU na carreira
    Talvez, se eu tivesse feito outra escolha naquela época, pudesse ter ganhado 100 milhões de dólares

    • Comigo foi parecido. Em 2009, por curiosidade, acho que usei CUDA v1 numa GeForce 8 para criar uma forma bem inicial de um toolkit de bioinformática otimizado para GPU
      Depois fui fazer outra coisa e perdi uma fortuna
    • Considerando que é uma ideia de ciência da computação de 1970, isso parece pouco provável. Ideias que valiam a pena tentar em GPUs de propósito geral provavelmente já estavam na mira de todo mundo
      Há 10 anos fiz uma implementação de hashcash em GPU, mas hoje ela provavelmente quase não teria valor
    • Como projeto de graduação com honras, fiz o porte para CUDA de um algoritmo de aprendizado de máquina e depois simplesmente dei de ombros e fui para programação embarcada
    • Você provavelmente teria ganhado muito mais se tivesse comprado Bitcoin

  • Nota para o autor: a parte interativa é muito boa. Para mostrar o ponto principal com mais clareza, seria legal dar um exemplo de duas strings que geram colisão de hash, colocar uma no primeiro campo de entrada e testar a outra no segundo campo
    Assim dá para mostrar por que a resposta é sempre “pode estar no conjunto”, e não “está”

    • "bloom" e "demonstrators " colidem. Atenção ao espaço no fim da segunda string
      Ambas colidem com fnv: 7, murmur: 12

  • Há um truque de que gosto. Às vezes, quando preciso fazer muitos testes de pertencimento em um conjunto que pode ser pequeno, dá para anexar especulativamente um filtro de Bloom de 64 bits com uma função de hash bem simples
    Parece extremamente bobo, mas o custo é tão baixo que vale a aposta. Mesmo quando não dá certo, só adiciona cerca de 10 ns para inserção e teste de pertencimento; quando dá certo, pode eliminar uma quantidade enorme de trabalho

    • O Chromium também faz isso em vários lugares. O texto só linkou o exemplo do Safe Browsing usando murmur, mas o Blink, o renderizador, normalmente usa rapidhash e emprega esses microfiltros em vários pontos
      Por exemplo, em certos casos de querySelector(), na pré-filtragem de consultas por hash em buckets de CSS e para rejeitar rapidamente elementos ao procurar determinados atributos Aria para acessibilidade. É surpreendente que filtros minúsculos de 32 ou 64 bits funcionem, mas na prática eles costumam ser eficazes. Também há alguns filtros de Bloom maiores. Alguns desses fui eu que adicionei

  • Pedi ao ChatGPT para criar um em Python, e ele usou a abordagem de cortar o digest md5 básico e tratá-lo como vários hashes. Para usos sem importância, parece aceitável

  • Outra visualização de filtros de Bloom pode ser vista no fim desta página:
    https://www.chrislaux.com/hashtable.html

  • Achei que já tinha visto isso antes, mas na verdade era esta outra página: https://bdupras.github.io/filter-tutorial/
    Esta página acrescenta um pouco mais de informação ao comparar filtros de Bloom e filtros cuckoo

  • Recentemente implementei um recurso de prevenção de spam em mensagens de log com filtros de Bloom. No logger, eu fazia hash da mensagem e a colocava no filtro; se o item já estivesse lá, a mensagem não era impressa
    A cada poucos segundos, eu percorria o filtro e limpava todos os bits, e isso funcionou bem porque eu não precisava me preocupar com limpar atomicamente todos os bits do filtro. Se, enquanto mensagens estavam chegando, apenas alguns desses bits fossem limpos, isso já bastava para que a mensagem voltasse a ser registrada. A implementação anterior contava o número de mensagens vistas até saturar em N, e tinha o efeito de que, se uma mensagem específica fosse repetida, ela só aparecia abaixo da velocidade com que o filtro era limpo
    Foi bastante satisfatório conhecer filtros de Bloom apenas em teoria e então encontrar um uso real tão natural para eles, gerando uma grande melhoria

  • Para ler mais, o texto de Eli Bendersky sobre filtros de Bloom também foi bom:
    https://eli.thegreenplace.net/2025/bloom-filters/

  • Os conceitos necessários para entender filtros de Bloom, conjuntos e tabelas hash parecem se sobrepor em algo como 95%. Um conjunto é uma tabela hash para teste de pertencimento que se importa apenas com chaves, não com valores, e um filtro de Bloom é um conjunto que aproveita o fato de que hashing muitos-para-um “comprime” o espaço de chaves por meio de colisões
    É como usar deliberadamente uma função de hash com muitas colisões. Se uma determinada chave já foi hasheada alguma vez, o resultado necessariamente será positivo, mas pode haver outra chave que produziu o mesmo hash. Não é bug, é feature

    • Fico feliz por não ser o único a entender filtros de Bloom como tabelas hash que não rastreiam os dados reais, apenas os buckets que contêm dados
    • O ponto essencial que falta nessa explicação é que filtros de Bloom usam várias funções de hash para reduzir colisões. Por exemplo, se houver 3 hashes, para uma chave ser considerada presente no conjunto, os três hashes precisam bater
      Isso reduz a possibilidade de colisões de falsos positivos, mantendo a garantia de que não há falsos negativos
    • Se você entendeu corretamente filtros de Bloom, já está quase lá para entender também projeções aleatórias e algumas implementações de hash sensível à localidade