A série sobre algoritmos para estimar o número de valores distintos em um multiconjunto continua com um artigo sobre o algoritmo state of the art HyperLogLog. No entanto, todas as ideias por trás desse algoritmo vêm do LogLog descrito antes, então, se você quer continuar a leitura, certifique-se de conhecer bem o LogLog.

O algoritmo LogLog tinha dois problemas principais:

Outliers

A estimativa final do LogLog é muito sensível a outliers, valores que estão muito distantes dos demais. Em geral acontece que a maioria dos comprimentos máximos dos sufixos de zeros de cada grupo é aproximadamente a mesma, por exemplo fica entre 12 e 15, mas aí, bum! — um sufixo de zeros tem comprimento 27. Essa grande diferença bagunça a estimativa final do número de valores distintos, porque a média aritmética clássica não lida muito bem com isso. No fundo, é o mesmo princípio de quando alguns altos executivos e diretores elevam, com os seus salários altos, o salário médio do país.

Os autores do algoritmo tentaram resolver isso se livrando dos outliers e não incluindo na média alguns dos maiores máximos, mas essa não era uma solução muito boa. Depois tentaram outro procedimento — em vez da média aritmética, usaram a média harmônica, que tem propriedades muito melhores quando temos valores distantes da média.

Resultados muito ruins para cardinalidades pequenas

O LogLog tem resultados péssimos quando precisa estimar a cardinalidade de multiconjuntos pequenos. Se temos no multiconjunto poucos elementos distintos, o LogLog nos devolve uma estimativa absurdamente grande. Os autores resolveram isso de forma esperta — quando temos na entrada um multiconjunto de baixa cardinalidade, não se usa o algoritmo LogLog, mas um algoritmo totalmente diferente, a saber, o velho conhecido Linear counting. Pois é, mas como saber que temos na entrada um multiconjunto de pequena cardinalidade, se justamente não conhecemos a cardinalidade?

Deixamos o LogLog estimar o número de elementos distintos e, quando descobrimos que essa estimativa é relativamente baixa, descartamos a estimativa e a calculamos de novo com o algoritmo Linear counting. Vamos relembrar rapidamente como o Linear counting funciona. No começo alocamos um vetor (de bits) zerado de algum tamanho previamente dado, tipicamente uma potência de dois. Percorremos todos os elementos do multiconjunto, calculamos o hash de cada um e o convertemos em um número inteiro i do intervalo de 0 até o comprimento do vetor menos 1. Guardamos, então, 1 no índice i do vetor. Por fim, calculamos o número de zeros e de uns no vetor e, por meio de uma fórmula simples, estimamos a cardinalidade.

O algoritmo LogLog, porém, não usa nenhum vetor de bits em que “guardaria” os hashes calculados. Em vez disso, usa um vetor em que guarda os comprimentos máximos dos sufixos. O vetor pode ser, por exemplo, assim:

[2, 5, 9, 0, 5, 4, 4, 0]

em que cada número indica o comprimento máximo do sufixo de zeros no grupo dado dos hashes calculados. Um valor diferente de zero na posição i significa, porém, necessariamente que, entre os valores do multiconjunto, existe um elemento cujo hash (de três bits) é igual a i. Em outras palavras, podemos converter esse vetor em um vetor de bits para o linear counting mantendo os zeros e convertendo qualquer número positivo em um. Do vetor anterior obteríamos, assim, o vetor de bits:

[1, 1, 1, 0, 1, 1, 1, 0]

Agora podemos aplicar o algoritmo Linear counting e estimar com ele a cardinalidade.

Isso tem, porém, um probleminha. Nós guardamos no vetor o maior sufixo de zeros, mas e se em algum grupo de valores todos os hashes terminarem em um? Se, por exemplo, usarmos os últimos três bits como identificador do grupo a que o hash pertence, então o comprimento do sufixo de zeros deste hash “01001100” seria zero — porque o vetor “01001” termina em um. No vetor de máximos guardaríamos, assim, zero no índice 4 (100₂=4₁₀). No algoritmo linear counting isso se manifestaria como se não tivéssemos encontrado um valor cujo hash fosse quatro, o que não é verdade.

Por isso modificamos o algoritmo para que ele não guarde no vetor de máximos o comprimento do maior sufixo de zeros, mas o índice do “primeiro um da direita para a esquerda” (para constar — indexamos a partir de um), o que equivale a somarmos um ao comprimento do sufixo de zeros. Com isso conseguimos que um zero no índice i signifique que nenhum valor tem hash igual a i, e esse vetor pode então ser usado para o linear counting.

Implementação do HyperLogLog

Vamos passo a passo:

def alpha(num_buckets):
    return (0.7213 / (1 + 1.079 / num_buckets))

A função alpha devolve a correção da estimativa calculada, já conhecemos isso da vez passada; só que, no caso do HyperLogLog, o alpha tem outro valor, dependendo do número de grupos.

def trailing_zeroes(number):
    if number == 0: 
        return 0
    zeroes = 0
    while (number & 1) == 0:
        zeroes += 1
        number = number >> 1
    return zeroes

Função que devolve o número de bits zero no final do número.

def count_maxims(values, k):
    num_buckets = 2 ** k  
    max_zeroes = [0] * num_buckets

    for value in values:
        h = hash(value)
        bucket_index = h & (num_buckets - 1)
        bucket_hash = h >> k
        num_zeros = trailing_zeroes(bucket_hash) + 1
        max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)

    return max_zeroes

Função que percorre todos os valores, os divide em num_buckets grupos e, para cada grupo, calcula o índice do primeiro um da direita para a esquerda (o comprimento do maior sufixo de zeros mais um).

def linear_counting(number_of_ones, num_buckets):
    number_of_zeros = num_buckets - number_of_ones
    Z = float(number_of_zeros) / num_buckets
    p = (-num_buckets) * log(Z)
    return p

Função levemente modificada para calcular o algoritmo Linear counting.

def estimate_cardinality(values, k): 
    num_buckets = 2 ** k   
    max_zeroes = count_maxims(values, k)
    estimate = float(alpha(num_buckets) * (num_buckets**2)) / sum(2**(-r) for r in max_zeroes)
    number_of_ones = sum(1 if x > 0 else 0 for x in max_zeroes)

    if (estimate <= 2.5 * num_buckets) and (number_of_ones < num_buckets):
        return linear_counting(number_of_ones, num_buckets)
    else:
        return estimate

A função principal, que junta tudo isso. Primeiro calcula a estimativa por meio do LogLog modificado, usa na quarta linha, no lugar da média aritmética, a média harmônica e, por fim, aplica a correção na forma do Linear counting, se a estimativa calculada for menor do que 2,5 vezes o número de grupos (neste momento esperamos que a estimativa padrão do LogLog seja pior do que se usássemos o Linear counting) e se no vetor de máximos houver pelo menos um zero (não podemos usar no Linear counting um vetor em que só há uns, veja o artigo anterior). E quais são os resultados do HyperLogLog?

Executamos o código de teste, que estima a cardinalidade de conjuntos que têm, sucessivamente, cardinalidade 10, 100, …, 1.000.000:

for x in range(1, 7):
    num_values = 10**x
    values = (str(uuid4()) for _ in xrange(num_values))
    cardinality = estimate_cardinality(values, 14)
    print "Cardinality: %s, relative error: %s" % (cardinality, num_values / cardinality)

Resultados:

Cardinality: 10.0030530001, relative error: 0.999694793165
Cardinality: 100.306423257, relative error: 0.996945128268
Cardinality: 1003.0892434, relative error: 0.99692027063
Cardinality: 10013.1348931, relative error: 0.998688233677
Cardinality: 100520.045562, relative error: 0.994826449206
Cardinality: 998088.420332, relative error: 1.0019152408

Vemos que os resultados se desviam sempre do resultado correto em menos de um por cento. E isso é bom!

Outras melhorias do HyperLogLog

O HyperLogLog recebeu várias outras melhorias interessantes. Um dos problemas que restam é o alto consumo de memória. Isso soa bem estranho, depois de termos elogiado o consumo de memória até os céus da última vez e calculado que, para guardar o vetor de máximos, nos bastam 768 bytes. Só que o problema surge se você quer calcular a cardinalidade não de um único multiconjunto enorme, mas, em paralelo, de vários milhões de multiconjuntos pequenos, ou se quer guardar esses vetores de máximos calculados em um banco de dados para algum malabarismo posterior.

Se, por exemplo, calculássemos ao mesmo tempo a cardinalidade de um bilhão de multiconjuntos, precisaríamos, com a implementação atual, de 1.000.000.000 vezes 768 bytes, que são 768 GB. Por um lado, não é ruim … mas, por outro, conseguimos implementar o HyperLogLog melhor.

Representação esparsa

Imagine que definimos k=12, isto é, usamos 12 bits para identificar os grupos e obtemos, assim, 2¹² grupos de hashes diferentes. No começo do algoritmo precisamos alocar um vetor de comprimento 4.096 (veja a linha 3 da função count_maxims). E digamos que o nosso multiconjunto tenha três elementos diferentes. Isso significa que no vetor definimos algum valor em três posições diferentes, e os 4.093 valores restantes do vetor ficam zerados, os 4.093 restantes simplesmente não foram usados de forma alguma. Isso não é muito eficiente, né?

Para evitar ter um vetor que será em sua maior parte zerado e não usado, mas que mesmo assim ocupa um pedaço valioso de memória, podemos, no começo, guardar os valores como pares [índice, valor]. Um exemplo para entender melhor. Considere este vetor:

[7, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Podemos representá-lo de forma muito mais eficiente em memória como dois pares:

[0, 7], [4, 12]

Em vez de ter alocado na memória um monte de espaço não utilizado, podemos alocar aos poucos apenas o espaço de que realmente precisamos. Chamamos essa representação de esparsa (sparse). No entanto, em algum momento essa representação ficaria mais custosa em memória do que simplesmente guardar em um vetor — aí podemos converter a representação esparsa em um vetor clássico sem perda de informação.

Offsets

A prática mostrou que todos os valores no vetor são aproximadamente iguais. O vetor de máximos costuma ser, por exemplo, assim:

[12, 13, 11, 13, 15, 12, 14, 11, 12, ...,  13, 14, 11]

Todos os valores ficam em algum lugar em torno do número 13. Outra estratégia para reduzir o tamanho desse vetor é subtrair de cada elemento algum valor fixo e memorizá-lo. Podemos subtrair, por exemplo, oito:

[4, 5, 3, 5, 7, 4, 6, 3, 4, ..., 5, 6, 3]

Neste ponto, cada valor do vetor consome uma quantidade menor de memória — no primeiro vetor precisamos guardar números de 0 a 15, para o que precisamos de 4 bits, enquanto para o segundo vetor nos bastam 3 bits, porque guardamos apenas números de 0 a 7. É claro que isso pressupõe uma implementação do vetor no nível de bits individuais. No momento em que quisermos ler os valores do vetor, precisamos somar de volta a eles o valor anotado.

…e um monte de outras melhorias. A pesquisa nessa área ainda está em andamento, então com certeza podemos esperar outras ideias interessantes. Da próxima vez vamos falar sobre a união e a interseção de vetores HyperLogLog e, em algum momento num futuro próximo, vamos falar sobre por que pode ser útil guardar bilhões de vetores HyperLogLog.

Links e fontes

• Você pode ver toda a minha implementação no GitHub.
• HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm [PDF] — o artigo original em que o HyperLogLog foi apresentado.
• HyperLogLog in Practice: Algorithmic Engineering of a State of The Art Cardinality Estimation Algorithm [PDF] — versão aprimorada do HyperLogLog original, por exemplo com a representação esparsa mencionada.