Como o algoritmo HyperLogLog funciona?

Recentemente, aprendi sobre diferentes algoritmos no meu tempo livre, e um que me deparei que parece muito interessante é chamado de algoritmo HyperLogLog - que estima quantos itens exclusivos há em uma lista.

Isso foi particularmente interessante para mim porque me trouxe de volta aos meus dias no MySQL quando vi o valor de "Cardinalidade" (que eu sempre assumi até recentemente que era calculado não estimado).

Então, eu sei como escrever um algoritmo em O ( n ) que calculará quantos itens exclusivos há em uma matriz. Eu escrevi isso em JavaScript:

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j++) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique++;
    }
    return numUnique;
}

Mas o problema é que meu algoritmo, enquanto O ( n ), usa muita memória (armazenando valores em Table).

Estive lendo este artigo sobre como contar duplicatas em uma lista em O ( n ) tempo e usando memória mínima.

Explica que, usando hash e contando bits ou algo que se possa estimar com uma certa probabilidade (assumindo que a lista seja distribuída uniformemente) o número de itens exclusivos em uma lista.

Eu li o jornal, mas não consigo entender. Alguém pode dar uma explicação mais leiga? Eu sei o que são hashes, mas não entendo como eles são usados ​​nesse algoritmo HyperLogLog.

O principal truque por trás desse algoritmo é que, se você, observando um fluxo de números inteiros aleatórios, vê um número inteiro cuja representação binária começa com algum prefixo conhecido, há uma chance maior de que a cardinalidade do fluxo seja 2 ^ (tamanho do prefixo) .

Ou seja, em um fluxo aleatório de números inteiros, ~ 50% dos números (em binário) começam com "1", 25% começam com "01", 12,5% começam com "001". Isso significa que, se você observar um fluxo aleatório e vir um "001", há uma chance maior de que esse fluxo tenha uma cardinalidade de 8.

(O prefixo "00..1" não tem significado especial. Está lá apenas porque é fácil encontrar o bit mais significativo em um número binário na maioria dos processadores)

Obviamente, se você observar apenas um número inteiro, a chance de esse valor estar errado é alta. É por isso que o algoritmo divide o fluxo em substreams independentes "m" e mantém o comprimento máximo de um prefixo "00 ... 1" visto de cada substream. Em seguida, estima o valor final usando o valor médio de cada sub-fluxo.

Essa é a idéia principal desse algoritmo. Há alguns detalhes ausentes (a correção para valores baixos de estimativa, por exemplo), mas tudo está bem escrito no artigo. Desculpe pelo terrível inglês.

Um HyperLogLog é uma estrutura de dados probabilística . Conta o número de elementos distintos em uma lista. Mas, em comparação com uma maneira simples de fazer isso (ter um conjunto e adicionar elementos ao conjunto), ele faz isso de maneira aproximada.

Antes de analisar como o algoritmo HyperLogLog faz isso, é preciso entender por que você precisa dele. O problema de maneira direta é que consome O(distinct elements)espaço. Por que existe uma grande notação O aqui em vez de apenas elementos distintos? Isso ocorre porque os elementos podem ter tamanhos diferentes. Um elemento pode ser 1outro elemento "is this big string". Portanto, se você tiver uma lista enorme (ou um fluxo enorme de elementos), será necessária muita memória.

Contagem Probabilística

Como se pode obter uma estimativa razoável de vários elementos únicos? Suponha que você tenha uma cadeia de comprimento mque consiste {0, 1}em igual probabilidade. Qual é a probabilidade de começar com 0, com 2 zeros, com k zeros? É 1/2, 1/4e 1/2^k. Isso significa que, se você encontrou uma string com kzeros, examinou aproximadamente os 2^kelementos. Portanto, este é um bom ponto de partida. Ter uma lista de elementos que são distribuídos igualmente entre 0e 2^k - 1você pode contar o número máximo do maior prefixo de zeros na representação binária e isso fornecerá uma estimativa razoável.

O problema é que a suposição de ter números uniformemente distribuídos de 0t 2^k-1é muito difícil de alcançar (os dados que encontramos geralmente não são números, quase nunca distribuídos uniformemente e podem estar entre quaisquer valores. Mas, usando uma boa função de hash, você pode assumir que os bits de saída seriam distribuídos uniformemente e a maioria das funções de hash tem saídas entre 0e 2^k - 1( SHA1 fornece valores entre 0e 2^160). Portanto, o que alcançamos até agora é que podemos estimar o número de elementos únicos com a cardinalidade máxima de kbits armazenando apenas um número de log(k)bits de tamanho.A desvantagem é que temos uma enorme variação em nossa estimativa.Uma coisa legal que quase criamosPapel probabilístico de contagem de 1984 (é um pouco mais inteligente com a estimativa, mas ainda estamos perto).

LogLog

Antes de avançarmos, precisamos entender por que nossa primeira estimativa não é tão boa. A razão por trás disso é que uma ocorrência aleatória de elemento de prefixo 0 de alta frequência pode estragar tudo. Uma maneira de aprimorá-lo é usar muitas funções de hash, contar no máximo para cada uma das funções de hash e, no final, calculá-las. Essa é uma excelente idéia, que melhorará a estimativa, mas o papel LogLog usou uma abordagem ligeiramente diferente (provavelmente porque o hash é meio caro).

Eles usaram um hash, mas o dividiram em duas partes. Um é chamado de balde (o número total de baldes é 2^x) e outro - é basicamente o mesmo que o nosso hash. Foi difícil para mim entender o que estava acontecendo, então vou dar um exemplo. Suponha que você tenha dois elementos e sua função hash, que fornece valores 0aos 2^102 valores produzidos: 344e 387. Você decidiu ter 16 baldes. Então você tem:

0101 011000  bucket 5 will store 1
0110 000011  bucket 6 will store 4

Ao ter mais baldes, você diminui a variação (você usa um pouco mais de espaço, mas ainda é pequeno). Usando habilidades matemáticas, eles foram capazes de quantificar o erro (que é 1.3/sqrt(number of buckets)).

HyperLogLog

O HyperLogLog não apresenta novas idéias, mas usa principalmente muita matemática para melhorar a estimativa anterior. Os pesquisadores descobriram que, se você remover 30% dos maiores números dos baldes, melhorará significativamente a estimativa. Eles também usaram outro algoritmo para calcular a média dos números. O papel é pesado em matemática.

E quero terminar com um artigo recente, que mostra uma versão aprimorada do algoritmo hyperLogLog (até agora não tinha tempo para entendê-lo completamente, mas talvez mais tarde aprimore essa resposta).

A intuição é que, se sua entrada for um grande conjunto de números aleatórios (por exemplo, valores de hash), eles deverão ser distribuídos uniformemente por um intervalo. Digamos que o intervalo seja de até 10 bits para representar um valor de até 1024. Em seguida, observe o valor mínimo. Digamos que seja 10. Então a cardinalidade será estimada em cerca de 100 (10 × 100 × 1024).

Leia o jornal para a lógica real, é claro.

Outra boa explicação com o código de exemplo pode ser encontrada aqui:
Algoritmos muito legais: estimativa de cardinalidade - Nick's Blog