Rails on the road

A cosa serve un filtro di Bloom?

Un filtro di Bloom è utile quando si tratta di fare ricerche con un dataset di grandi dimensioni. I filtri di Bloom esistono in più tipi, la gemma BloomFilter è l’implementazione di un filtro di Bloom semplice e potete installarla semplicemente con:

    1 gem install bloomfilter

Che cosa è un Bloom Filter?

Il filtro di Bloom (da H. Bloom che lo concepì nel 1970), è una struttura dati probabilistica space-efficient ed è utilizzato per stabilire se un elemento è appartenente ad un dataset prestabilito di elementi. Sono possibili falsi positivi ma non falsi negativi. Quindi più elementi appartegono al dataset di elementi prestabiliti, più aumenta la possibilità di falsi positivi.

Come funziona?

Un Bloom Filter è un vettore di bit definito da due parametri:

• Un array di M bit
• K funzioni di Hash indipendenti con codominio in [1,M]

Inizialmente gli M bit dell’array sono settati tutti a zero (0), il passo successivo è riempire il filtro di Bloom con quegli elementi che creano il dataset sul quale poi fare i confronti. Per riempire il filtro si deve applicare k funzioni hash ad ogni elemento, i k risultati dell’hash sono la posizione di ogni bit che verranno settati ad uno (1). Può succedere che più di una chiave setti lo stesso bit ad uno.

Questo è quello che succede applicando ad esempio 3 funzioni di hash all’elemento bicchiere:

Per creare il dizionario di parole iniziali si adotterà questo procedimento per tutti gli elementi che voglio inserire:

A questo punto vedere se un oggetto appartiene al set è semplice: si applicano k funzioni hash all’elemento da cercare per ottenere le k posizioni dei bit sull’array e si controlla che queste siano settate ad uno (1), se tutti i bit sono uno (1) allora l’oggetto potrebbe appartenere al set, altrimenti no.

Vediamo come potrebbero essere alcuni risultati di ricerca:

Adesso invece vediamo un esempio di falso positivo, applicando 3 funzioni hash alla parola cartella si ottengono 3 bit dell’array di Bloom; Controllando sul “filtro pieno”, i bit, sono tutti impostati ad “1″ (colorati nel disegno). Il problema però è che i colori per modo di dire non corrispondono, cioè il fatto che la parola cartella sia un falso positivo dipende dal fatto che i 3 bit sono settati ad uno perchè la parola piatto e la parola bicchiere del dataset avevano impostato quei bit ad uno (1).

Il filtro di Bloom consente l’inserimento e la ricerca ma non la rimozione, infatti per rimuovere un oggetto si dovrebbe settare a zero (0) i k bit risultanti dall’applicazione delle k funzioni di hash, ma questo potrebbe accidentalmente cancellare altri oggetti del dataset.

Il filtro di Bloom descritto precedentemente, implementato nella libreria Ruby, è un filtro semplice che ad esempio non funziona per mappare un dataset multilivello come potrebbe essere un documento XML. I filtri di Bloom esistono anche BBF (Breadth Bloom Filters) e DBF (Depth Bloom Filters) con differenti prestazioni a seconda della grandezza del dataset.

Alcuni risultati

I ragazzi di Rapleaf hanno dumpato 40 Milioni di hash su un file creando un filtro di Bloom; come risultato hanno ottenuto un un array di 100MB di bit, successivamente hanno controllato una lista di 500 Milioni di hash creando una lista di possibili match. Hanno impiegato circa 8 ore contro i 20 giorni previsti per fare gli stessi controlli usando comparazioni su database Mysql. Hanno trovato che dei match trovati il 98% erano positivi veri, mentre il 2% erano falsi positivi.