LogLog: como estimar o número de valores distintos
Depois das partes anteriores sobre o Linear Counting e o Min Value, chegamos enfim ao quase melhor dos melhores algoritmos probabilísticos para estimar o número de valores distintos em um conjunto de dados, o LogLog. Melhor do que ele só o seu irmãozinho HyperLogLog, que parte do LogLog, mas sobre ele falaremos da próxima vez.
Vamos relembrar o enunciado do problema. Na entrada temos algum conjunto de dados/multiconjunto, por exemplo um vetor/gerador de IDs. Nesse vetor há valores que aparecem várias vezes, e queremos calcular o número de valores distintos nesse vetor. Vamos chamar esse número de cardinalidade. Esperamos que essa cardinalidade seja realmente grande; caso contrário, podemos usar algoritmos convencionais.
A ideia do algoritmo LogLog
Imagine que temos um conjunto de vetores binários. Não se assuste; por exemplo, este 0001011001001100 é um vetor binário de comprimento 16. Digamos que temos vetores binários de comprimento 32 e que temos ao todo um milhão deles, todos gerados de forma totalmente aleatória. Quantos vetores terminarão em zero?
Isso, é claro, não podemos saber com exatidão, mas, se realmente geramos esses vetores de forma aleatória, aproximadamente metade deles deveria terminar em zero, isto é, 500 mil. Quantos vetores terminarão em 00? Um quarto. Em 000? Um oitavo. E assim por diante. Podemos representar isso mais ou menos assim:
padrão do vetor proporção entre todos os vetores
...xxxxxx0 50%
...xxxxx00 25%
...xxxx000 12,5%
...xxx0000 6,25%
... ...
Se perguntarmos por um sufixo (sufixo é a cadeia com que termina outra cadeia — o oposto de prefixo) de comprimento d, esperamos encontrar v vetores que terminam com esse sufixo. Calculamos o valor de v como:
em que N é o número de todos os vetores no conjunto. Um sufixo de comprimento 3 (por exemplo …010) deveria aparecer em 1/2^3 N = 1/8 N vetores, isto é, 12,5% de todos os vetores.
Agora vem algo de fundir a cuca. Considere um multiconjunto de 1024 vetores distintos. Quantos vetores deveriam terminar com o sufixo 0000000000? (dez zeros) Substituímos na fórmula e obtemos
Hã, um só! Em mil vetores binários gerados aleatoriamente, deveria haver exatamente um vetor que termina com dez zeros. E como usar essa informação para estimar o número de elementos distintos? Podemos proceder no sentido inverso. E se percorrermos todos os vetores binários que temos na entrada e descobrirmos que no conjunto existe um único vetor que termina com dez zeros? Então podemos estimar que no conjunto havia 1024 vetores!
Generalizando e montando o algoritmo
O objetivo deveria ser encontrar um sufixo que esteja contido em um único vetor, sendo esse sufixo o mais curto possível. Isso, porém, só é possível com muita dificuldade, porque, para realmente encontrar tal vetor, teríamos de guardar todos os sufixos, o que não queremos, porque ocuparia memória demais. Em vez disso, nos contentamos em procurar a maior sequência de zeros no final do vetor.
Percorremos, então, todos os vetores, para cada vetor calculamos quantos zeros ele contém no final e, em uma variável, guardamos o máximo desses valores. Depois de percorrermos todos os vetores, saberemos o comprimento do maior sufixo formado apenas por zeros. Denotamos esse comprimento pela letra d. Agora modificamos a fórmula anterior de modo a isolar a variável N, isto é, para que ela seja a saída do algoritmo, e não a entrada. Nesse caso, podemos substituir v por um, porque esperamos encontrar exatamente um vetor assim, isto é, esperamos que valha v=1.
Se encontrarmos, assim, o comprimento d do maior sufixo de zeros, estimamos a cardinalidade pela fórmula N=2d.
Como obter vetores binários aleatórios?
Com vetores binários aleatórios o algoritmo já funciona, mas como aplicar esse procedimento a dados reais? Como de costume, aqui também usamos alguma função hash adequada. Se temos na entrada um conjunto de dados, por exemplo IDs (strings), primeiro aplicamos hash neles. A saída de uma função hash de n bits são n bits que, do ponto de vista prático, parecem vetores binários gerados aleatoriamente.
Neste ponto já podemos escrever o nosso algoritmo:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def count_unique(values):
max_zero_suffix_length = 0
for value in values:
zeroes_length = trailing_zeroes(hash(value))
max_zero_suffix_length = max(zeroes_length, max_zero_suffix_length)
return 2 ** max_zero_suffix_length
A função trailing_zeroes devolve o número de zeros no final do número. Como ela faz isso? Se você não entendeu pelo código, melhor nem perguntar. E qual é a taxa de acerto da função? Para um conjunto que continha cem mil elementos distintos, a função devolveu a estimativa 524.288.
Pois é…
Quer dizer, não está lá muito bom, né? Mas não tem problema! Vamos tentar melhorar o algoritmo exatamente como fizemos com o Min Value anterior. Dividimos os dados de entrada em vários grupos disjuntos, para cada grupo calculamos o maior sufixo de zeros e, por fim, calculamos o comprimento médio do sufixo de zeros e o usamos para estimar o número de valores distintos.
Podemos dizer, por exemplo, que os dois últimos bits de cada vetor determinarão o número do grupo a que o vetor pertence. Considere estes seis vetores:
1101110111111011 1110110010100101
1011001111110010 1111101100000011
1010101000100000 0110010110011000
Podemos dividi-los em quatro grupos, conforme a terminação que têm:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011
Em seguida calculamos o comprimento do maior sufixo de zeros em cada vetor, mas pulando os bits que usamos como número do grupo. Marcamos em verde os “sufixos” de zeros:
00 01 1010101000100000 1110110010100101 0110010110011000 10 11 1011001111110010 1101110111111011 1111101100000011 00: 3 01: 0 10: 2 11: 6
No final estão os comprimentos dos maiores sufixos de zeros de cada grupo. Com esses comprimentos podemos calcular a média aritmética, que dá 2,75. Substituímos o valor na fórmula e obtemos
Obtemos o número médio de elementos distintos em cada grupo. O que, é claro, não bate de jeito nenhum, mas não vamos nos atormentar com isso: para conjuntos pequenos, o algoritmo LogLog dá resultados péssimos.
Para estimar a cardinalidade do conjunto inteiro, precisamos ainda multiplicar esse valor pelo número de grupos: 6,727 · 4 = 26,908. O algoritmo calculou que no conjunto há aproximadamente 27 valores distintos. Havia seis, então está totalmente fora, mas isso, agora, realmente não importa.
Implementação do algoritmo
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets
O parâmetro k determina quantos bits serão tomados como índice do grupo. Esse parâmetro determina a precisão do algoritmo — quanto maior o k, maior a precisão. Na variável bucket_index fica guardado o número do grupo. Como funciona aquela mágica do lado direito do sinal de igualdade?
Na variável num_buckets está o número de grupos, que é sempre uma potência de dois. Se, por exemplo, k = 3, então num_buckets=8. O número 8 tem, no sistema binário, a forma 1000. Se subtrairmos um, obtemos o número 7, que tem a forma 0111. Depois de subtrair um de num_buckets, sempre obtemos um número que tem no final k uns e, antes deles, só zeros. Em seguida fazemos o E lógico bit a bit (é aquele operador &). Para o vetor 1110110010100101, essa operação seria assim:
1110110010100101
& 0000000000000111
------------------
0000000000000101
O objetivo de toda essa mágica é obtermos um número que contém só zeros no início e cujos últimos k bits são iguais aos do hash h dado.
Depois calculamos bucket_hash, que é o hash original do qual removemos os últimos k bits deslocando o hash inteiro k bits para a direita. O deslocamento se comporta assim: simplesmente move todos os bits do número k posições para a direita, e à esquerda o número é preenchido com zeros. (O deslocamento de bits para a direita em um se comporta do mesmo modo que dividir o número por dois e descartar o resto.) Do vetor 1110110010100101, depois de um deslocamento de três, obteríamos 0001110110010100. Esse vetor ficaria guardado na variável bucket_hash.
Depois calculamos o número de zeros no final desse vetor e, se esse valor for maior do que o valor máximo atual guardado no vetor max_zeroes no índice bucket_index, sobrescrevemos o valor.
No final, só calculamos o número médio de zeros em todos os grupos e calculamos qual é o número médio de elementos distintos em cada grupo (2 ** average_max_zeros). Como temos ao todo num_buckets grupos, multiplicamos esse valor justamente pelo número de grupos, obtendo a estimativa final do número de elementos distintos. Ufa, e nem doeu. Resultados para vários conjuntos de dados que contêm 250.000 valores distintos e k=10:
331774.56203
323349.39265
307343.444439
309430.914045
294512.379123
Nããão, ainda errado :-(. Mas já estamos bem perto, não se preocupe. Observe que todos os resultados são maiores do que o resultado correto. Durante o algoritmo, vários erros se acumulam, e por isso a estimativa é visivelmente maior do que o resultado correto. No entanto, esses erros são bastante constantes e dá para estimar o tamanho do erro que ocorreu. Quando multiplicamos a estimativa pela constante empírica 0,79402, obtemos resultados bem melhores:
263435.63774306054
256745.88475195298
244036.84175345476
245694.33437001088
233848.71927124445
Tentei também um multiconjunto que tem cardinalidade de um milhão; resultados:
Resultado Erro
1017297.17411 1.01729717411
1022820.99717 1.02282099717
984108.725487 0.984108725487
1018675.32683 1.01867532683
1007020.2853 1.0070202853
Beleza! O erro fica abaixo de 2,5%, o que é um desempenho razoável. E esse, senhoras e senhores, é o algoritmo LogLog. A implementação final, já com a constante empírica, é esta:
def trailing_zeroes(number):
if number == 0:
return 0
zeroes = 0
while (number & 1) == 0:
zeroes += 1
number = number >> 1
return zeroes
def estimate_cardinality(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)
max_zeroes[bucket_index] = max(max_zeroes[bucket_index], num_zeros)
average_max_zeros = float(sum(max_zeroes)) / num_buckets
return (2 ** average_max_zeros) * num_buckets * 0.79402
Da próxima vez veremos como modificar esse algoritmo para obter o lendário e melhor dos melhores HyperLogLog. Por enquanto, vamos ver o quanto o algoritmo consome de memória.
Consumo de memória
O algoritmo é muito eficiente no que diz respeito à memória ocupada. A única coisa que precisamos guardar é o vetor que mantém os máximos. O comprimento desse vetor é influenciado pelo valor de k, isto é, pelo número de bits do vetor que tomamos como índice do grupo. Para um dado k, temos ao todo 2k grupos diferentes, e por isso o vetor de máximos tem comprimento 2k. Na implementação, chamamos esse valor de num_buckets.
Qual deve ser o tamanho de uma célula do vetor? Vamos guardar nela os comprimentos dos sufixos de zeros. Posso adiantar que um hash de 64 bits provavelmente basta para todos os multiconjuntos imagináveis do mundo, de modo que nesse vetor precisamos ser capazes de guardar números de 0 (vetor formado só por uns) a 64 (vetor formado só por zeros). Além disso, se supusermos que k será sempre maior do que zero, então basta guardar números de 0 a 63. Para isso, veja só, bastam 6 bits, porque 26 = 64.
Sim, basta-nos um “vetor” em que cada célula tem o tamanho de 6 bits. Posso ainda adiantar que o valor k=10 basta para estimarmos com razoável precisão cardinalidades na casa das centenas de milhões. Um algoritmo configurado assim criaria um vetor de tamanho 210 = 1024, no qual cada célula ocupa 6 bits. No total, esse vetor ocuparia 6.144 bits, que são 768 bytes. Nem um quilobyte.
E isso é tudo.
Não precisamos guardar mais nada; podemos descartar os hashes calculados logo em seguida, basta-nos conhecer o número de zeros no final do vetor.
Observe que, se você usasse uma função hash maior, que devolvesse, por exemplo, 128 bits, o consumo de memória não mudaria muito. Precisaríamos guardar números de 0 a 127, para o que bastam 7 bits. O consumo de memória é determinado, portanto, sobretudo pelo parâmetro k, isto é, pelo número de grupos.
O LogLog é adequado sobretudo onde precisamos contar multiconjuntos de cardinalidade realmente grande. Como se viu também no exemplo simples acima, o LogLog não se sai muito bem com multiconjuntos que têm pequena cardinalidade. Isso, no entanto, também tem remédio: por exemplo, se descobrirmos que o multiconjunto tem baixa cardinalidade, usamos para a estimativa outro algoritmo, por exemplo o Linear Counting descrito antes. Disso também falaremos da próxima vez.
Fontes:
- Loglog Counting of Large Cardinalities [PDF]
- Damn Cool Algorithms: Cardinality Estimation (daí vem, mais ou menos copiado, o código do LogLog)
Capítulos: Linear counting: como estimar o número de valores distintos, Min Value: como estimar o número de valores distintos, LogLog: como estimar o número de valores distintos, HyperLogLog: como estimar com muita precisão o número de valores distintos
