Come trovare il numero di elementi in un flusso di dati - dummy

Anche se un filtro Bloom può tracciare oggetti provenienti da uno stream, non può sapere quanti oggetti ci sono. Un vettore di bit riempito da uno può (a seconda del numero di hash e della probabilità di collisione) nascondere il vero numero di oggetti sottoposti a hashing allo stesso indirizzo.

Conoscere il numero distinto di oggetti è utile in varie situazioni, ad esempio quando si desidera sapere quanti utenti distinti hanno visto una determinata pagina del sito Web o il numero di query distinte del motore di ricerca. Memorizzare tutti gli elementi e trovare i duplicati tra di loro non può funzionare con milioni di elementi, in particolare provenienti da uno stream. Quando si desidera conoscere il numero di oggetti distinti in uno stream, è comunque necessario fare affidamento su una funzione hash, ma l'approccio prevede l'utilizzo di uno schizzo numerico.

Disegnare significa prendere un'approssimazione, che è un valore inesatto ma non completamente sbagliato come risposta. Il ravvicinamento è accettabile perché il valore reale non è troppo lontano da esso. In questo algoritmo intelligente, HyperLogLog, che si basa sulla probabilità e sull'approssimazione, si osservano le caratteristiche dei numeri generati dallo stream. HyperLogLog deriva dagli studi degli scienziati informatici Nigel Martin e Philippe Flajolet. Flajolet ha migliorato il loro algoritmo iniziale, Flajolet-Martin (o l'algoritmo LogLog), nella versione più robusta di HyperLogLog, che funziona così:

1. Un hash converte tutti gli elementi ricevuti dallo stream in un numero.
2. L'algoritmo converte il numero in binario, lo standard numerico di base 2 utilizzato dai computer.
3. L'algoritmo conta il numero di zeri iniziali nel numero binario e le tracce del numero massimo che vede, ovvero n.
4. L'algoritmo stima il numero di elementi distinti passati nello stream utilizzando n. Il numero di elementi distinti è 2 ^ n.

Ad esempio, il primo elemento nella stringa è la parola dog. L'algoritmo lo inserisce in un valore intero e lo converte in binario, con un risultato di 01101010. All'inizio del numero appare solo uno zero, quindi l'algoritmo lo registra come il numero massimo di zeri finali visti. L'algoritmo vede quindi le parole pappagallo e lupo, i cui equivalenti binari sono 11101011 e 01101110, lasciando n invariato. Tuttavia, quando passa la parola cat, l'output è 00101110, quindi n diventa 2. Per stimare il numero di elementi distinti, l'algoritmo calcola 2 ^ n, cioè 2 ^ 2 = 4. La figura mostra questo processo.

Contando solo zeri iniziali.

Il trucco dell'algoritmo è che se il tuo hash produce risultati casuali, equamente distribuiti (come in un filtro Bloom), guardando la rappresentazione binaria, puoi calcolare la probabilità che appaia una sequenza di zeri. Poiché la probabilità che un singolo numero binario sia 0 è uno su due, per calcolare la probabilità di sequenze di zeri, basta moltiplicare la probabilità 1/2 quante volte la lunghezza della sequenza di zeri:

• 50 percento (1/2) probabilità per i numeri che iniziano con 0
• 25 percento (1/2 * 1/2) di probabilità per i numeri che iniziano con 00
• 12. 5 percento (1/2 * 1/2 * 1/2) probabilità per i numeri che iniziano con 000
• (1/2) ^ k probabilità per i numeri che iniziano con k zeri (si usano i poteri per calcoli più veloci di molte moltiplicazioni del stesso numero)

Minore è il numero di HyperLogLog, maggiore è l'imprecisione. L'accuratezza aumenta quando si utilizza il calcolo HyperLogLog più volte utilizzando diverse funzioni hash e si calcola la media delle risposte da ciascun calcolo, ma l'hashing richiede molte volte tempo e gli stream sono veloci. In alternativa, puoi utilizzare lo stesso hash ma dividere il flusso in gruppi (ad esempio separando gli elementi in gruppi non appena arrivano in base al loro ordine di arrivo) e per ogni gruppo, tieni traccia del numero massimo di zeri finali. Alla fine, si calcola la stima dell'elemento distinto per ciascun gruppo e si calcola la media aritmetica di tutte le stime. Questo approccio è la media stocastica e fornisce stime più precise rispetto all'applicazione dell'algoritmo all'intero flusso.