o problema
Contar quantos elementos distintos existem num conjunto é trivial se você puder guardá-los: um hash set com n entradas responde exato. O problema aparece quando n não cabe na memória e o dado passa uma vez só. O paper abre com o caso de rede: um stream de pacotes, cada um com um par origem-destino no header, e a pergunta “quantos fluxos ativos distintos há nesta fatia de tempo?”. Worms e vírus se propagam abrindo muitas conexões diferentes; escondidos num tráfego enorme eles passam despercebidos, e só ficam expostos quando alguém mede cardinalidade. A mesma pergunta reaparece em texto em linguagem natural, dado biológico, banco estruturado grande e no grafo da internet — para este último, o paper cita ganhos computacionais de mais de 500 vezes atribuídos a estimadores probabilísticos.
Antes do HyperLogLog já havia duas famílias de estimadores. Uma observa padrões de bits no início dos valores hasheados: ver um prefixo com ρ−1 zeros seguidos de um 1 sugere que a cardinalidade é pelo menos 2^ρ. É a linha do Probabilistic Counting, de 1985, e do LogLog, de 2003. A outra observa estatísticas de ordem, como o menor valor real visto, já que a esperança desse mínimo é 1/(n+1). Nas duas, uma observação isolada tem variância alta demais para prever coisa alguma. Rodar m experimentos em paralelo resolveria, mas exigiria m hashes por elemento e um conjunto de m funções hash independentes, para o qual não se conhece construção. A saída, também de 1985, é o stochastic averaging: os primeiros b bits do hash escolhem um dentre m = 2^b substreams, cada substream mantém seu próprio observável, e tudo isso com uma função hash só e trabalho constante por elemento. Com esse arranjo o LogLog chegou a 1,30/√m de erro padrão, e ali travou.
a ideia
O HyperLogLog não troca o observável nem o formato do estado. Troca a média.
O LogLog combina os máximos por algo que equivale a uma média geométrica. Aqui a combinação é a média harmônica dos 2^Max. A razão está na forma da distribuição: o máximo de ρ tem cauda direita lenta, então basta um registrador azarado ter visto um hash com muitos zeros à esquerda para ele sozinho puxar a estimativa para cima. A média geométrica ainda sente esse outlier; a harmônica quase não sente, porque soma inversos e um valor enorme entra na conta como quase zero. A inspiração veio de uma nota de Chassaing e Gérin, e o efeito é redução de variância. O ganho sai de graça em tempo e em espaço: mesma passada, mesmo estado, só a última linha do algoritmo é outra. 1,30 vira 1,04 — ou, pelo outro lado, o HyperLogLog iguala a precisão do LogLog gastando 64% da memória.
como funciona
para cada v do stream:
x := h(v)
j := 1 + <x1 x2 ... xb> # endereço: os b primeiros bits
M[j] := max(M[j], ρ(x_{b+1} x_{b+2} ...)) # ρ = posição do 1 mais à esquerda
Z := 1 / Σ_j 2^(-M[j]) # média harmônica dos 2^M[j], a menos de m
E := α_m · m² · ZA intuição do fator: cada substream recebe cerca de n/m elementos, seu máximo fica perto de log2(n/m), a média harmônica dos 2^Max fica na ordem de n/m, e m²Z na ordem de n. A constante α_m corrige um viés multiplicativo sistemático e tende a 1/(2 log 2) = 0,72134.
O teorema principal mostra duas coisas sobre multisets ideais: o estimador é assintoticamente quase sem viés, com flutuação abaixo de 5·10⁻⁵ para m ≥ 16, e o erro padrão é β_m/√m, com β_m descendo de 1,106 (m = 16) até 1,03896, que é a raiz de 3 log 2 − 1. A prova passa por poissonização, transformada de Mellin e depoissonização por ponto de sela — a média harmônica acopla as variáveis e quebra o caminho usual da análise.
Na prática, os registradores vão de 0 a L + 1 − log2 m, então 5 bits bastam com hash de 32 bits. Com m = 2.048 isso dá 1,5 kB e 2% de erro típico. E dois estimadores se fundem tomando o max campo a campo: é isso que faz o algoritmo paralelizar de forma ótima.
o que isso custou
O algoritmo analisado não é o algoritmo que você roda. Com registradores iniciados em −∞, a estimativa vira zero assim que um substream fica vazio, o que pelo problema do colecionador de figurinhas acontece sempre que n é bem menor que m log m. Iniciando em 0, o estimador cru devolve cerca de 0,7·m quando n = 0. O programa prático então cola duas correções por fora da teoria: abaixo de 2,5·m ele conta bins vazios e usa m log(m/V), o estimador do Hit Counting; acima de 2³²/30 ele desfaz colisões de hash com −2³² log(1 − E/2³²). O regime assintótico bonito só começa em n = 2,5·m.
O resto do preço é o de sempre em estrutura probabilística. A garantia é estatística, não dura: as estimativas caem dentro de σ, 2σ e 3σ em 65%, 95% e 99% dos casos, e não há como saber em qual caso você está. Tudo depende de a função hash parecer uniforme — os autores modelam isso como ideal multiset e assumem a hipótese, apontando CRC, aritmética modular e sha1 como escolhas que a sustentam. Restam flutuações oscilantes minúsculas, calculáveis mas não canceladas. O custo de tempo é dominado pelo hash: três a quatro vezes mais lento que um wc -l. E o próprio paper recusa o título de ótimo: para a classe de algoritmos baseados em estatísticas de ordem, o limite inferior de Chassaing-Gérin fica cerca de 4% abaixo, então o certo é near-optimal.
onde isso aparece hoje
A linhagem direta é Probabilistic Counting Algorithms for Data Base Applications, de 1985: mesmo observável, mesma ideia de stochastic averaging, vinte e dois anos depois. Do lado de fora, o HyperLogLog é irmão de Space/Time Trade-offs in Hash Coding with Allowable Errors — um responde pertinência com falso positivo, o outro responde cardinalidade com erro relativo, e os dois compram espaço vendendo exatidão, que é exatamente o eixo formalizado em Designing Access Methods: The RUM Conjecture.
Hoje o algoritmo está exposto como recurso de primeira classe em bancos e engines: o Redis oferece os comandos PFADD, PFCOUNT e PFMERGE, e contagem distinta aproximada é função nativa em praticamente todo warehouse analítico. O PFMERGE é a pista do porquê: como o estado é um vetor de máximos, esboços calculados em máquinas diferentes, dias diferentes ou partições diferentes se combinam sem tocar nos dados originais. Cardinalidade deixou de ser uma agregação que precisa ver tudo junto e virou um valor que se guarda, se soma e se versiona.