Cos'è Lossy Counting?

Question

Qualcuno può spiegarmi l'algoritmo Lossy Counting? È un algoritmo di streaming sulla ricerca della frequenza di elementi in un flusso. Grazie.

Answer 1

Dire che stai guardando il traffico per i profili di Facebook. Hai miliardi di visite. Si desidera individuare i profili a cui si accede più spesso. Puoi tenere un conteggio per ogni profilo, ma in questo caso avresti un numero molto elevato di conteggi da tenere sotto controllo, la maggior parte dei quali sarebbe priva di significato.

Con il conteggio delle perdite, si rimuovono periodicamente gli elementi di conteggio molto bassi dalla tabella. I profili a cui si accede più spesso non hanno quasi mai un conteggio basso, e se lo facessero, probabilmente non rimarrebbero lì a lungo.

L'algoritmo consiste essenzialmente nel raggruppare gli input in blocchi o blocchi e nel conteggio all'interno di ciascun blocco. Quindi riduci il conteggio di ogni elemento di uno, eliminando tutti gli elementi i cui conteggi scendono a zero.

I profili di hit più frequenti verranno inclusi nel conteggio e resteranno lì. Ogni profilo che non viene colpito molto spesso scenderà a zero in pochi blocchi e non dovrai più seguirli.

Si noti che i risultati finali dipendono dall'ordine, dando un peso maggiore ai conteggi elaborati per ultimi. In alcuni casi, questo ha perfettamente senso ed è un rialzo piuttosto che un aspetto negativo. (Se vuoi sapere quali sono i profili più popolari ora, vuoi pesare gli accessi oggi più degli accessi del mese scorso.)

Ci sono un gran numero di affinamenti all'algoritmo. Ma l'idea di base è questa: per trovare i colpitori pesanti senza dover tracciare ogni elemento, periodicamente elimina i tuoi conteggi di tutti gli elementi che non sembrano essere colpevoli pesanti in base ai dati finora.

Answer 2

È possibile trovare una spiegazione di come Lossy Counting (e Sticky Sampling) funziona on this blog post e un open-source version here.

Gli articoli visualizzati più di frequente "sopravvivono". Data una soglia di frequenza f, un errore di frequenza e, e un numero totale di elementi N, l'uscita può essere espressa come segue: Elementi con conteggio superiore a fN - eN.

Nel peggiore dei casi sono necessari contatori (1/e) * log (eN).

Ad esempio, potremmo voler stampare le pagine di Facebook di persone che hanno colpito più del 20%, con una soglia di errore del 2% (regola generale: errore = 10% della soglia di frequenza).

Per frequenza f = 20%, e = 2%, verranno emessi tutti gli elementi con frequenza reale superiore a f = 20% - non ci sono falsi negativi. Ma noi sottovalutiamo. La frequenza di uscita di un elemento può essere inferiore alla sua frequenza reale di almeno il 2%. I falsi positivi potrebbero apparire con una frequenza compresa tra il 18% e il 20%. Infine, non verrà prodotto alcun elemento con frequenza inferiore al 18%.

finestrino di dimensioni 1/e Data, le seguenti garanzie contenere:

• Le frequenze sono sottovalutati da al massimo e * N
• Nessun falsi negativi
• I falsi positivi sono vere frequenza di almeno f N - e N