O HyperLogLog contou bilhões de itens distintos em kilobytes

A cardinalidade exata — quantos usuários, endereços IP ou consultas de busca distintos apareceram — normalmente exige memória proporcional ao número de itens distintos, o que é impossível na escala da internet. Em 2007, Philippe Flajolet e colegas do INRIA publicaram o HyperLogLog, um esboço probabilístico que estima cardinalidades acima de um bilhão com cerca de 2 por cento de precisão usando aproximadamente 1,5 kilobytes de memória.

O truque se baseia numa intuição de cara ou coroa: faça o hash de cada elemento para um número aleatório uniforme e observe a maior sequência de zeros à esquerda. Uma sequência de n zeros é rara — probabilidade 2^-n —, então, quando ela aparece, o conjunto provavelmente é grande o suficiente para tê-la produzido, e 2^n é uma boa estimativa da cardinalidade. O HyperLogLog divide o fluxo em muitos subconjuntos, mantém um registrador por subconjunto guardando sua maior sequência de zeros e os combina com uma média harmônica para que valores atípicos não distorçam a estimativa.

O método descende do algoritmo de Flajolet-Martin de 1984 e do algoritmo LogLog. A engenharia que o tornou pronto para produção veio no artigo de 2013 'HyperLogLog in Practice', de Heule, Nunkesser e Hall, no Google, que corrigiu problemas de viés e de esparsidade para cardinalidades grandes e pequenas.

O Redis transformou o HyperLogLog em recurso de produto: seus comandos PFADD, PFCOUNT e PFMERGE estimam até 2^64 elementos distintos com até 12 KB de memória por chave e erro padrão de 0,81 por cento, e os esboços se fundem, de modo que contagens diárias se combinam sem reler o fluxo bruto.

Estimar contagens a partir dos zeros à esquerda do hash

Um hash transforma dados arbitrários em um número aleatório uniforme com a mesma cardinalidade

A maior sequência de zeros à esquerda é uma estimativa natural e observável do tamanho do conjunto

Dividir em registradores mais uma média harmônica cancela o ruído

Os esboços se fundem, então contagens diárias se combinam sem armazenar o fluxo bruto

Quando a resposta só precisa ser aproximada, pare de armazenar os dados — armazene um pequeno esboço cuja aleatoriedade revela o tamanho, e troque um erro limitado por escala ilimitada.

O HyperLogLog tornou-se um bloco de construção padrão em análise de dados e bancos de dados: o Redis o oferece como tipo de dados, e as melhorias do artigo do Google de 2013 foram o que o tornou utilizável em escala em sistemas de produção. A lógica do esboço — manter um pequeno registro de evidências, não os dados — também sustenta estruturas posteriores como MinHash e Count-Min Sketch.