Rails on the road

I Bloom Filter, di cui ho già parlato nel post “Bloom Filter: una nuova libreria Ruby” dopo aver letto un articolo dei ragazzi di Rapleaf, hanno largo uso anche nel P2P perchè per stabilire se un elemento appartiene ad un dataset basta applicare k-funzioni hash a prescindere dal numero di elementi presenti nel dataset.

Nel caso del P2P o di web application, dove il Bloom Filter deve essere passato tra proxies, il punto di vista cambia non si cercherà più di ottimizzare il numero k di hash per ridurre al minimo i falsi positivi ma si cercherà di ottimizzarlo in funzione della grandezza dei dati che devono essere trasmessi.

Probabilità di falsi positivi

Per proseguire nella discussione è necessario definire la probabilità di trovare falsi positivi in un filtro di Bloom che, se per assunto si ha che tutte le funzioni hash sono casuali, è:

Nel nostro caso la probabilità che un bit sia a 1 o a 0 è indipendende per cui p = 1/2. Quindi in un Bloom Filter standard la probabilità di falsi positivi è:

(0.5)^k

Per un filtro standard il numero k di funzioni hash per minimizzare la probabilità di falsi positivi(f) è:

k = ln2 m/n

quindi

f = (0.5)^m ln2/n

Se mettiamo z = m allora possiamo dire che f = (0.6185)^z/n dove z è l’array compresso al massimo a m*H(p) dove H(p) è:

H(p) = −p log2 p − (1 − p) log2 (1 − p)

Compressione dell’array

Il valore di k = ln2 m/n su un filtro di Bloom compresso non è buono in quanto massimizza f e questo chiaramente non va bene. Va scelto un numero k di funzioni hash minore di ln2 m/n per questo motivo il filtro copresso è migliore perchè utilizza anche un numero minore di funzioni di hash.

Se vogliamo che la probabilità di falsi positivi rimanga costante possiamo dire (ricordando che la f di un filtro compresso tende a (0.5)^z/n) che:

f = (0.5)^m*ln2/n = (0.5)^z/n

Se m è l’array di bit, allora z (l’array di bit compresso) è uguale a m ln2; in questo modo mantenendo costante la probabilità di falsi positivi riesco a comprimere l’array di bit di circa il 30%.

Questa compressione è quella massima ottenibile ma nella pratica ci sono alcune restrizioni da tenere in considerazione quali la grandezza dei packet da spedire fissata, per evitare di intasare la rete con invii multipli, quindi l’array non deve superare determinate dimensioni; se non si conosce il numero degli elmenti del dataset in anticipo un’errata predizione può peggiorare di molto la compressione.

Approfondimenti

La dimosrazione che fa vedere come k = ln2 * (m/n) non è istantanea, e per questo non l’ho riscritta, cmq se vi interessa l’argomento ci sono alcuni articoli molto interesanti. Chiaramente la mia spiegazione è molto all’acqua di rose come si suol dire, ma spero che comunque sia di aiuto per iniziare a studiare i Bloom Filter con compressione.

Questo articolo è molto chiaro o almeno mi sembra!