o problema
Em rede, listas são caras de dois jeitos diferentes. Um proxy que quer saber o que os proxies vizinhos têm em cache precisaria receber a lista de URLs deles — periodicamente, porque o cache muda. Um router que quer saber se já viu um pacote precisaria guardar todos os pacotes que encaminhou. Um nó de rede peer-to-peer que quer localizar um arquivo precisaria de um índice do que cada vizinho carrega. Em todos os casos a informação existe, é útil, e não cabe: ou estoura a banda da atualização, ou estoura a memória do dispositivo que precisa responder na velocidade do fio.
A estrutura que resolve isso tinha trinta anos quando este survey saiu. Bloom a propôs em 1970 para hifenização, e ela circulou por décadas em banco de dados — spell-checkers do UNIX, dicionário de senhas proibidas, semi-join distribuído, differential files. O que Broder e Mitzenmacher fazem aqui é catalogar a redescoberta da estrutura pela literatura de redes no fim dos anos 1990, e mais que isso: dar um enquadramento comum a aplicações que pareciam não ter nada a ver umas com as outras.
a ideia
O enquadramento cabe numa frase, que os autores chamam de princípio do filtro de Bloom: onde uma lista ou conjunto é usado e o espaço é caro, considere um filtro de Bloom se o efeito do falso positivo puder ser mitigado.
O deslocamento é sutil e é o valor real do artigo. A conversa de engenharia não é mais sobre a estrutura — a matemática dela é meia página, e está fechada desde 1970. A conversa é sobre a semântica do erro naquele ponto específico do sistema. No cache compartilhado, um falso positivo é um pedido a um proxy que não tem a página: atraso, nada mais, e o cache já erra sozinho porque as atualizações são periódicas. No roteamento por recurso, é uma requisição descendo o galho errado da árvore, e alguém precisa saber voltar. No IP traceback, é uma bifurcação no caminho reconstruído. Cada aplicação do survey é, na verdade, um argumento sobre por que aquele erro específico era barato.
como funciona
Um array de m bits, todos em 0, e k hash functions com imagem em {1..m}. Para inserir x, sete os k bits h_i(x). Para consultar y, teste os k bits: se algum for 0, y definitivamente não está no conjunto. Falso negativo é impossível; falso positivo, não.
Depois de n inserções, a probabilidade de um bit continuar 0 é p = e^(-kn/m), e a taxa de falso positivo é f = (1-p)^k. Há duas forças opostas em k: mais hash functions dão mais chances de achar um 0 para quem está fora, e ao mesmo tempo enchem o array mais rápido. A derivada zera em k = ln 2 · (m/n) — exatamente onde p = 1/2. Nesse ponto f = (1/2)^k ≈ 0,6185^(m/n). O limite inferior de informação para qualquer representação com taxa de erro ε é n·log₂(1/ε) bits, então o filtro está a um fator de log₂ e ≈ 1,44 do ótimo.
Três variações importam. Contar em vez de marcar: cada posição vira um contador pequeno, incrementado na inserção e decrementado na remoção, e o survey mostra que 4 bits bastam — a chance de algum contador chegar a 16 é da ordem de 1,37 × 10⁻¹⁵ vezes m. Comprimir: se a métrica for bits transmitidos e não bits em memória, vale usar um array maior e mais esparso, porque um filtro meio cheio é incompressível por construção. E somar: dois filtros do mesmo tamanho com as mesmas hash functions se unem por OR, e o produto interno deles estima o tamanho da interseção.
o que isso custou
A análise inteira supõe hash functions perfeitamente aleatórias. Os autores dizem explicitamente que qual função usar na prática continua uma questão aberta, e registram que MD5 era a escolha popular. Toda a garantia de taxa de erro herda essa suposição.
O counting Bloom filter compra remoção pagando em bits por posição e introduz uma falha nova: se um contador satura e é travado no máximo, ele pode depois cair a zero quando deveria continuar positivo — e aí o filtro passa a produzir falso negativo, que o filtro comum nunca produz.
Há um custo teórico admitido com franqueza: o filtro dá erro constante com bits constantes por elemento, e a comunidade de teoria queria erro assintoticamente nulo, que só se consegue com Θ(log n) bits por elemento. Por isso a estrutura ficou de fora dos papers de algoritmos por décadas e viveu na prática.
E o custo operacional que reaparece em quase toda aplicação da survey: manter os filtros atualizados. Em cache compartilhado, em P2P, em roteamento por recurso, o desafio declarado não é o falso positivo, é a frequência das atualizações e o tráfego que elas geram. Um filtro desatualizado erra por um motivo que a matemática acima não modela.
onde isso aparece hoje
O caso do Summary Cache virou produto: o proxy Squid o adotou com o nome de Cache Digests. O padrão de projeto que ele estabeleceu — anunciar por difusão um resumo probabilístico em vez da lista — reaparece toda vez que um sistema distribuído precisa que os nós tenham uma ideia aproximada do que os outros guardam.
A linhagem começa em Space/Time Trade-offs in Hash Coding with Allowable Errors e segue nas variantes que o próprio survey cataloga na seção final: spectral Bloom filter, space-code, Bloomier filter e o count-min sketch, este último notável por dar garantias teóricas usando só hash functions pairwise independent, que são baratas de verdade. A ideia de conservative update de Estan e Varghese — incrementar um contador só até o máximo que aquele fluxo poderia justificar — é o tipo de truque que só aparece quando alguém leva a estrutura para dentro de um router.
Fora de redes, o filtro é peça padrão em motores de armazenamento LSM-tree, onde evita ir ao disco procurar uma chave que não está no arquivo. E a insatisfação com os dois pontos fracos listados acima — o fator 1,44 e a falta de remoção limpa — é exatamente o que motiva o Cuckoo Filter uma década depois.