Bloom Filter: cos'è e come funziona.

Ehila!
Buon anno a tutti!
Oggi vi racconto un po' del Bloom filter!
Concepito da Burton Howard Bloom nel 1970, il Bloom filter è una struttura dati probabilistica efficiente usata per testare se un elemento appartiene a un insieme o no. I falsi positivi sono possibili ma non i falsi negativi.
Una query quindi può ritornare “può darsi che ci sia dentro l’insieme (forse!)” oppure “sicuramente non c’è dentro l’insieme”. Elementi possono essere inseriti nell’insieme ma non possono essere rimossi (a meno che non si utilizzi un counting filter) e più elementi vengono aggiunti all’insieme, maggiore è la probabilità di ottenere un falso positivo.
Il Bloom filter è usato per velocizzare le risposte in un sistema di archiviazione basato su chiave. Un esempio esplicativo è mostrato in Figura 1 dove gli elementi sono memorizzati in un disco che ha tempi di accesso lenti.
In questo caso il Bloom filter fa delle decisioni molto veloci che possono far risparmiare del tempo evitando una ricerca inutile su disco. Tuttavia alcuni accessi non necessari al disco possono essere fatti per la possibilità di falsi positivi. Il tempo di risposta generale però è migliore con i Bloom Filter anche se, per questo tipo di utilizzo, c’è un costo in termini di memoria da sostenere.

Figura 1

Descrizione dell’algoritmo

Un Bloom filter vuoto è un array di m bit tutti settati a 0. Devono anche essere definite k funzioni hash differenti, ognuna delle quali mappa un elemento del set in una delle m posizioni dell’array con una distribuzione uniforme.
Per aggiungere un elemento, vengono calcolate tutte le k funzioni hash per ottenere le k posizioni nell’array. Poi vengono settati a 1 i bit in quelle k posizioni.
Importante proprietà dei Bloom filter è che il tempo necessario sia per aggiungere un elemento che per controllare se un elemento è nell’insieme è costante: O(k).
:-O
Inoltre è completamente indipendente dal numero di elementi che già sono nell’insieme.

Dato un insieme di oggetti S = {x1, ..., xn}, un array B di m bit dove bi ∈ {0, 1}, supponiamo di avere un insieme H di k funzioni hash {h1, ..., hk} ognuna delle quali è definita come hi : U ⊇ S → [1; m] e indicizzano l’array B.
Un breve pezzo di pseudocodice mostra in modo molto semplice come l’array B viene costruito:

Algorithm 1: build
Data: S, H, B
Result: B inizializzato

begin
  for each s in S do
    for each h in H do
      B[h(s)]=1;
    end
  end
end

La procedura build è Θ(|S|) = Θ(n) per quanto riguarda il tempo e Θ(|B|) = Θ(m) per quanto riguarda lo spazio.

Formalmente:
∀i. bi = 1 ⇔ ∃(j, t)| hj(xt) = i

Per testare un elemento sull’insieme, vengono calcolate le funzioni hash sull’elemento e poi vengono controllate le k posizioni dell’array di m bit.
Se anche solo uno dei bit controllati nell’array è 0 allora si può dire con certezza che l’elemento non è all’interno dell’insieme.
Se invece tutti i bit controllati sono settati a 1 allora vuol dire che o l’elemento è all’interno dell’insieme oppure i bit sono stati settati a 1 durante l’inserimento di altri elementi, restituendo quindi un falso positivo.
Per quanto riguarda la ricerca lo pseudocodice è del tipo:

Algorithm 2: search
Data: H, B, y (the query)
Result: “found”, “not found”

begin
  for each h in H  do
    if B[h(y)]=0  then
      return “not found”;
    end
  end
  return “found”;
end

La procedura search impiega O(1) in tempo e O(1) di spazio.

Formalmente:
y ∈ S ⇔ bhi(y) = 1 ∀i = 1, ..., k.

Problema della rimozione

Rimuovere un elemento dal Bloom filter semplice è impossibile perch´e i falsi negativi non sono permessi.
Infatti se volessimo eliminare un elemento x dal Bloom filter, si dovrebbe settare nuovamente a 0 i k bit ottenuti dalle k hash functions. Ma chi ci garantisce che uno o più di quei k bit non siano stati settati a 1 anche da un altro elemento y?
Ipotizziamo che effettivamente y abbia dei bit in comune con x. Nel caso in cui si procedesse con l’eliminazione di x, e quindi con il settaggio a 0 dei suoi bit nel bit array, quando si presenterà una query che chiederà al Bloom filter se y è presente, lui risponderà di no creando quindi un falso negativo.

Probabilità di Falso Positivo

Come già abbiamo detto in precedenza, i falsi positivi ci possono essere in quanto può esistere un xj = y tale che h...(xj)=h...(y). E per questo che quando un Bloom filter restituisce un esito positivo, vuol dire che probabilmente y ∈ S. Come calcolare questa probabilità?
Assumiamo che le funzioni hash selezionino ogni posizione dell’array in modo del tutto equiprobabile. Dopo il build, la probabilità p che bi = 0 sarà data da:

P (bi = 0) = (1 − 1/m)kn ≈ e−kn/m = p

E quindi la probabilità di un falso positivo è:

(1 − e−kn/m)k = (1 − p)k = ε

Come possiamo vedere dalla precedente approssimazione, la probabilità di un falso positivo decrementa all’aumentare di m (il numero di bit dell’array B) mentre incrementa al decrescere di n (numero degli elementi inseriti nel Bloom filter).
Fissati m e n, possiamo ora trovare il valore ottimale di k (il numero delle funzioni hash utilizzate dal filtro) che minimizza la probabilità di falsi positivi.
Dall'equazione precedente ricaviamo dunque:

k = ln 2(m/n).

Se p = 0.5 allora la possiamo scrivere come

ε = 0.5k = (0.6185)m/n

A seconda della probabilità di falsi positivi che vogliamo, dato n si può fissare m.
In generale scegliere m = O(n) è una buona scelta.
Qua sotto una tabella che mostra l'andamento della probabilità di FP al variare della dimensione del Bloom filter.

m ε %
n 0.61 61%
2n 0.38 38%
5n 0.09 9%
10n 0.008 0.8%

Altre proprietà

A differenza degli insiemi basati sulle tabelle hash, ogni Bloom filter può rappresentare l’intero universo di elementi. In questo caso tutti i bit sono uguali a 1. Un’altra conseguenza di questa proprietà è che l’operazione di aggiunta di un elemento al filtro non fallisce mai. Tuttavia, il tasso dei falsi positivi incrementa progressivamente fino a che tutti i bit del filtro sono settati a 1 e quindi non è mai possibile ottenere un risultato negativo. A questo punto un Bloom filter cessa di differenziare i diversi input, diventando quindi inutile.
Le operazioni di unione e di intersezione di Bloom filter della stessa dimensione e lo stesso insieme di funzioni hash, possono essere implementate rispettivamente con le due operazioni bit a bit OR e AND. L’operazione di unione tra più Bloom filter è senza perdita nel senso che il risultante Bloom filter è lo stesso che si otterrebbe creandolo da zero utilizzando l’unione dei due set.
L’intersezione soddisfa una proprietà più debole: la probabilità di avere un falso positivo nel Bloom filter risultante è al massimo la probabilità di falso positivo in uno dei Bloom filter costituenti. Tuttavia può avere una probabilità di falso positivo maggiore il Bloom filter costruito da zero usando l’intersezione dei due insiemi.

Implementazioni

C++
Per la mia tesi ho utilizzato questa libreria ancora in progress su boost
https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction

Boost.BloomFilters
Author(s): Dean Michael Berris, Alejandro Cabrera
Version: 0.1
State: On going
Last upload: 2009 June 08
Links: Boost Sandbox
Categories: Containers
Description:Bloom Filters
Download (documentazione all'interno del file)

JS
Un'altra implementazione molto carina fatta in js che dà anche un'idea del funzionamento del BF si può trovare nel link sottostante
http://www.jasondavies.com/bloomfilter/

Ecco un esempio di esecuzione della libreria sopracitata (entrate nel link per fare ulteriori prove ;D )

É tutto, a presto! 😉


Fonti:
Wikipedia
Bloom Filters: general theory and variants by G.Varavagna

Ingegnere Informatico e Ricercatore se compiace al Prodigioso Spaghetto Volante. Sono uno spartan racer, massimo esperto di serie tv, fotografo amatoriale e appena ne ho l’occasione preparo la valigia e parto

Bloom Filter: cos'è e come funziona. ultima modifica: 2013-01-09T23:33:49+01:00 da Andrea Salvi


Advertisment ad adsense adlogger