Como encontrar o número de elementos em um fluxo de dados - manequins

Mesmo que um filtro Bloom possa rastrear objetos que chegam de um fluxo, ele não pode dizer quantos objetos existem. Um pequeno vetor preenchido por um pode (dependendo do número de hashes e da probabilidade de colisão) ocultar o número real de objetos que estão sendo escondeu no mesmo endereço.

Conhecer o número distinto de objetos é útil em várias situações, como quando você quer saber quantos usuários distintos viram uma determinada página do site ou o número de consultas distintas do mecanismo de pesquisa. Armazenar todos os elementos e encontrar as duplicatas entre eles não pode funcionar com milhões de elementos, especialmente provenientes de um fluxo. Quando você quer saber o número de objetos distintos em um fluxo, você ainda precisa confiar em uma função de hash, mas a abordagem envolve a tomada de um esboço numérico.

Esboçar significa tomar uma aproximação, que é um valor inexato, porém não completamente errado, como uma resposta. A aproximação é aceitável porque o valor real não está muito longe disso. Neste algoritmo inteligente, HyperLogLog, que é baseado na probabilidade e na aproximação, você observa as características dos números gerados a partir do fluxo. O HyperLogLog deriva dos estudos de cientistas informáticos Nigel Martin e Philippe Flajolet. A Flajolet melhorou seu algoritmo inicial, Flajolet-Martin (ou o algoritmo LogLog), na versão HyperLogLog mais robusta, que funciona assim:

1. Um hash converte cada elemento recebido do fluxo em um número.
2. O algoritmo converte o número em binário, o padrão numérico da base 2 que os computadores usam.
3. O algoritmo conta o número de zeros iniciais no número binário e as faixas do número máximo que vê, que é n.
4. O algoritmo estima o número de elementos distintos passados ​​no fluxo usando n. O número de elementos distintos é 2 ^ n.

Por exemplo, o primeiro elemento na string é a palavra cão. O algoritmo o corta em um valor inteiro e converte-o em binário, com o resultado de 01101010. Somente um zero aparece no início do número, então o algoritmo o registra como o número máximo de zeros à esquerda vistos. O algoritmo então vê as palavras papagaio e lobo, cujos equivalentes binários são 11101011 e 01101110, deixando n inalterados. No entanto, quando a palavra cat passa, a saída é 00101110, então n se torna 2. Para estimar o número de elementos distintos, o algoritmo calcula 2 ^ n, ou seja, 2 ^ 2 = 4. A figura mostra esse processo.

Contando apenas os zeros à esquerda.

O truque do algoritmo é que, se o seu hash estiver produzindo resultados aleatórios, distribuídos igualmente (como em um filtro Bloom), ao analisar a representação binária, você pode calcular a probabilidade de aparecer uma seqüência de zeros. Como a probabilidade de um único número binário ser 0 é uma em duas, para calcular a probabilidade de seqüências de zeros, basta multiplicar essa 1/2 probabilidade quantas vezes o comprimento da seqüência de zeros:

• 50 por cento (1/2) de probabilidade para números que começam com 0
• 25 por cento (1/2 * 1/2) de probabilidade para números que começam com 00
• 12. Probabilidade de 5 por cento (1/2 * 1/2 * 1/2) para números que começam com 000
• (1/2) ^ k probabilidade para números que começam com k zeros (você usa poderes para cálculos mais rápidos de muitas multiplicações do mesmo número)

Quanto menor os números que o HyperLogLog vê, maior a imprecisão. A precisão aumenta quando você usa o cálculo HyperLogLog muitas vezes usando diferentes funções de hash e, em média, juntas as respostas de cada cálculo, mas hashing muitas vezes leva tempo, e os fluxos são rápidos. Como alternativa, você pode usar o mesmo hash, mas dividir o fluxo em grupos (por exemplo, separando os elementos em grupos à medida que eles chegam com base no seu pedido de chegada) e para cada grupo, você acompanha o número máximo de zeros à direita. No final, você calcula a estimativa do elemento distinto para cada grupo e calcula a média aritmética de todas as estimativas. Esta abordagem é a média estocástica e fornece estimativas mais precisas do que aplicar o algoritmo ao fluxo inteiro.