Papers
HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm
Philippe Flajolet, Éric Fusy, Olivier Gandouet, Frédéric Meunier · 2007 Conference on Analysis of Algorithms (AofA 07), DMTCS proc. AH, pp. 127-146, 2007
O problema: contar elementos distintos em um fluxo enorme com pouca memória
O artigo trata de estimar a cardinalidade de um multiconjunto, isto é, o número de elementos distintos de dados que são em geral fluxos de leitura única. Os autores citam aplicações em monitoramento de redes: o número de pares origem-destino distintos em janelas de tempo indica quantos fluxos ativos existem e ajuda a detectar ataques, e worms e vírus costumam se propagar abrindo muitas conexões diferentes, de modo que sua atividade aparece quando as cardinalidades são medidas. Calcular o valor exato exige armazenamento essencialmente proporcional ao número de elementos, e em muitas aplicações o conjunto é grande demais para caber na memória principal. Por isso o artigo relaxa a exigência: aceita-se uma estimativa aproximada, pois uma tolerância de poucos por cento costuma bastar. Todos os estimadores eficientes conhecidos dependem de aleatoriedade obtida por uma função de hash, e a análise supõe que os bits dos valores hasheados sejam independentes e tenham probabilidade 1/2 cada. O resumo do artigo apresenta a promessa do HyperLogLog: com m unidades de memória e uma única passada pelos dados, o erro relativo (erro padrão) é tipicamente cerca de 1,04 dividido pela raiz de m. Como exemplo, o artigo diz que cardinalidades acima de 10^9 podem ser estimadas com precisão típica de 2% usando apenas 1,5 kilobyte. O algoritmo melhora o LogLog, o melhor estimador anterior conhecido, cuja precisão pode ser igualada consumindo só 64% da memória original.
A ideia central: observável de padrão de bits e média estocástica
O HyperLogLog usa o mesmo observável do LogLog. Para uma cadeia binária, chama-se rho a posição do bit 1 mais à esquerda; ver um prefixo com muitos zeros é indício de que a cardinalidade é grande, pois um padrão com rho-1 zeros seguido de 1 sugere cardinalidade de pelo menos 2^rho. Um único observável tem variabilidade alta, e repetir o experimento com m funções de hash independentes seria caro e exigiria funções independentes para as quais não se conhece construção. A solução, chamada de média estocástica (técnica anterior de Flajolet e Martin), emula m experimentos com um só hash: os primeiros b bits do valor hasheado, com m igual a 2^b, escolhem um de m registradores, e o restante da cadeia alimenta o rho daquele registrador, que guarda o máximo de rho visto. Assim cada elemento custa um número constante de operações, e não proporcional a m. A novidade do HyperLogLog está na função de avaliação: em vez da média geométrica implícita no LogLog, ele calcula uma média harmônica das quantidades 2 elevado ao valor de cada registrador. O artigo atribui a inspiração a uma nota de Chassaing e Gérin e explica que a média harmônica doma distribuições com cauda direita de decaimento lento, atuando como redutor de variância. A estimativa é uma constante de correção vezes m ao quadrado dividido pela soma dos 2 elevados a menos o valor de cada registrador.
A garantia analítica: viés e erro padrão do Teorema 1
O resultado principal vale para multiconjuntos ideais, modelo no qual os valores hasheados são variáveis uniformes independentes no intervalo [0,1], com repetições e permutações arbitrárias. Para m registradores, com m maior ou igual a 3, o Teorema 1 afirma duas coisas. Primeiro, a estimativa é assintoticamente quase sem viés: o valor esperado dividido por n tende a 1 mais uma pequena oscilação, de módulo menor que 5 vezes 10^-5 quando m é pelo menos 16. Segundo, o erro padrão, definido como a raiz da variância dividida por n, tende a beta_m dividido pela raiz de m, mais uma oscilação de módulo menor que 5 vezes 10^-4 para m a partir de 16. As constantes beta_m são limitadas: beta_16 vale cerca de 1,106, beta_32 cerca de 1,070, beta_64 cerca de 1,054, beta_128 cerca de 1,046, e o limite beta_infinito é a raiz de 3 log 2 menos 1, aproximadamente 1,03896. A constante alfa_m da fórmula existe para corrigir um viés multiplicativo sistemático. O artigo também afirma que cada registrador precisa de no máximo log2 log2 N mais uma constante de bits quando se estimam cardinalidades até N. A prova usa técnicas padrão de análise de algoritmos, como poissonização, transformadas de Mellin e despoissonização por ponto de sela, e a não linearidade da média harmônica torna parte da análise não rotineira.
Do algoritmo ao programa: registradores, correções de faixa e custo
A análise supõe registradores iniciados em menos infinito, o que faz a estimativa valer 0 se algum registrador não for tocado, e portanto o algoritmo erra muito para cardinalidades pequenas. O programa prático da Figura 3 inicia os registradores em 0 e acrescenta duas correções. Na correção de faixa pequena, aplicada quando a estimativa bruta é no máximo 5m/2, o artigo usa o argumento de bolas e urnas, da mesma família do algoritmo Hit Counting de Whang e outros: se V registradores continuam em 0, a cardinalidade é estimada por m log(m/V), caso V seja diferente de zero. Sem isso, com n igual a 0 a versão bruta devolveria cerca de 0,7m. Simulações indicam que o regime assintótico é praticamente atingido a partir de n igual a 5m/2 para m maior ou igual a 16. Na correção de faixa grande, quando n se aproxima de 2^L os hashes de L bits colidem, e a fórmula inverte a relação esperada para obter n igual a menos 2^L log(1 menos E/2^L); com 32 bits, 2^32 é cerca de 4 vezes 10^9. Com hash de 32 bits, 5 bits bastam por registrador. Segundo o artigo, o tempo de execução é dominado pelo cálculo do hash, ficando de três a quatro vezes mais lento que uma varredura simples com wc -l. Os autores esperam estimativas aproximadamente gaussianas: dentro de 1, 2 e 3 desvios em cerca de 65%, 95% e 99% dos casos.
Por que é quase ótimo e o que o artigo diz sobre uso prático
O título fala em quase otimalidade, que o artigo justifica combinando dois fatos. Primeiro, manter contagens aproximadas com tolerância epsilon até a faixa N exige pelo menos da ordem de log log N bits: as cardinalidades ficam numa escala exponencial 1, (1+epsilon), (1+epsilon)^2 e assim por diante, com log base (1+epsilon) de N intervalos, e distingui-los pede ao menos o log2 desse número de bits. Segundo, Chassaing e Gérin mostraram que, para uma ampla classe de algoritmos baseados em estatísticas de ordem, a melhor precisão alcançável tem limite inferior próximo de 1 sobre a raiz de m. O HyperLogLog pode ser visto como mantendo estatísticas de ordem aproximadas e fica, com base só nesse resultado, cerca de 4% acima do ótimo teórico da classe de Chassaing e Gérin, usando unidades de memória tipicamente de 3 a 5 vezes menores. Em dados reais, o artigo mostra um experimento com m igual a 2048 (erro padrão de cerca de 2%) em 458 trechos de cerca de 40.000 linhas de despejos octais do fonte PostScript de um livro, com resultados em boa concordância com a análise. Os autores concluem que o algoritmo é fácil de implementar, exige apenas um bom hash e se distribui de forma ótima: dado um particionamento arbitrário do arquivo, basta coletar os registradores e aplicar um máximo componente a componente. Ele também se adapta ao modelo de janela deslizante.
Veja as ideias em ação
Pratique na escola de System Design os desenhos que usam este paper.