o problema
Um otimizador de query escolhe entre planos que custam ordens de grandeza diferentes, e a variável que separa os planos muitas vezes não é o tamanho da relação: é a cardinalidade, quantos valores distintos existem ali. O paper abre com o caso mais banal possível, a interseção de dois arquivos A e B. Ordenar A e buscar cada elemento de B custa O(a log a + b log a); ordenar os dois e fazer um merge custa outra coisa; eliminar duplicatas antes muda a conta de novo. O System R já guardava essa informação em catálogos — tamanho das relações e número de elementos diferentes nos campos-chave — para estimar seletividade e decidir qual algoritmo usar em cada operador relacional.
O jeito exato de obter esse número é construir a lista sem repetição: ordenar ou hashear o arquivo inteiro, com custo de disco e memória proporcional à cardinalidade. Em 1984, isso frequentemente custava mais do que o ganho que a estatística traria ao otimizador — você paga uma varredura completa para decidir como fazer a varredura. Amostrar também não resolve: estimar a cardinalidade de uma amostra e multiplicar pela razão entre os tamanhos depende de como as repetições estão espalhadas, e essa é justamente a informação que você não tem.
a ideia
Pare de olhar os elementos e olhe os bits dos hashes. Se o hash distribui uniformemente sobre L bits, a fração de valores que termina em exatamente k zeros é 2^-k-1: metade termina em 1, um quarto em 01, um oitavo em 001. Encontrar um hash terminado em vinte zeros é evidência de que você viu perto de um milhão de valores distintos. A raridade do padrão é o contador.
O “distintos” sai de graça nesse arranjo. O mesmo registro repetido produz o mesmo hash, marca o mesmo bit e não acrescenta nada. O resultado depende só do conjunto de valores hasheados, nunca da frequência com que aparecem — o oposto de uma amostragem, que é justamente sensível a isso. Os autores rodaram o procedimento no volume 1 do manual do Unix da instalação deles: 26.692 linhas, 16.405 distintas, e o bitmap resultante tinha o primeiro zero na posição 12 e o último um na 15, com 2^14 = 16.384 no meio do caminho.
como funciona
O procedimento base, chamado COUNT, mantém um vetor BITMAP de L bits. Para cada registro, calcula p(hash(x)) — a posição do 1-bit menos significativo, com ranks começando em zero — e acende esse bit. No fim, R é a posição do zero mais à esquerda. O valor esperado de R é log₂(φn), com φ = 0,77351, e o desvio padrão fica em 1,12: uma ordem binária de grandeza de erro, inútil sozinho.
A correção óbvia é usar m funções de hash e tirar a média dos m valores de R, o que reduz o desvio por √m — ao preço de calcular m hashes por registro. O paper substitui isso pelo que chama de stochastic averaging: um hash só, cujos bits de baixa ordem escolhem qual dos m bitmaps atualizar e cujo resto carrega a observação.
for x in M:
h = hash(x) # L bits
a = h mod m # escolhe o bitmap
i = p(h div m) # 1-bit menos significativo do resto
BITMAP[a][i] = 1
S = 0
for a in 0..m-1:
R = 0
while BITMAP[a][R] == 1 and R < L: R = R + 1
S = S + R
Z = m / phi * 2 ** (S / m) # phi = 0,77351O algoritmo resultante, PCSA, tem erro padrão de 0,78/√m e viés de 1 + 0,31/m, que se corrige dividindo por esse fator na última linha. São 20 ou 30 instruções de assembly por elemento; a versão em Pascal não otimizada dos autores rodava, num VAX 11/780, duas vezes mais rápido que o sort do sistema.
o que isso custou
Precisão é cara. Com 64 bitmaps o erro padrão é 9,7%; para chegar a 4,8% são 256, e 2,4% exige 1.024. Como o erro cai com a raiz, cada dígito a mais custa cem vezes mais memória — e os autores encerram o paper admitindo que não sabem se esse trade-off entre espaço e acurácia é o melhor possível, nem como provar que não é.
A garantia toda repousa sobre a hipótese de hash pseudo-uniforme, sustentada por evidência empírica (estudos sobre arquivos industriais grandes e as simulações do próprio paper), não por prova. L precisa satisfazer L > log₂(n/m) + 4, senão o vetor trunca e o algoritmo subestima — você precisa da ordem de grandeza antes de medir. As fórmulas são assintóticas e só valem quando n/m passa de 10 ou 20; cardinalidades pequenas exigem correções calculadas à parte. E deleção não existe: para suportar remoções é preciso guardar contadores em vez de bits, com o custo de memória correspondente.
onde isso aparece hoje
A propriedade que mais sobreviveu é a menos comentada no paper: bitmaps de execuções independentes se combinam com um OR lógico. Cada máquina processa seu pedaço, manda um vetor minúsculo para um coordenador, e a estimativa final não perde precisão nem se os pedaços se sobrepuserem. É isso que faz contadores de distintos serem hoje item de prateleira em sistemas analíticos e de streaming, onde count distinct exato é caro justamente por não ser combinável.
O desfecho direto veio do próprio Flajolet duas décadas depois: o HyperLogLog mantém a divisão por hash em m buckets inventada aqui e troca o observável e a média, chegando a muito mais precisão pelo mesmo espaço. Junto com o filtro de Bloom, este paper fundou o hábito de responder perguntas sobre conjuntos enormes guardando hashes em vez de dados.