Un filtro Bloom è una struttura di dati probabilistici efficiente sotto il profilo dello spazio, concepita da Burton Howard Bloom nel 1970, che viene utilizzata per verificare se un elemento è un membro di un set. Sono possibili falsi positivi, ma i falsi negativi non lo sono - in altre parole, una query restituisce "eventualmente nel set" o "sicuramente non nel set". Gli elementi possono essere aggiunti al set, ma non rimossi (anche se questo può essere risolto con un filtro di "conteggio"); più elementi vengono aggiunti all'insieme, maggiore è la probabilità di falsi positivi.
Bloom ha proposto la tecnica per le applicazioni in cui la quantità di dati sorgente richiederebbe una quantità di memoria eccessivamente grande se venivano applicate tecniche di hashing "convenzionali" prive di errori. Ha fornito l'esempio di un algoritmo di sillabazione per un dizionario di 500.000 parole, di cui il 90% segue semplici regole di sillabazione, ma il restante 10% richiede costosi accessi al disco per recuperare specifici pattern di sillabazione. Con sufficiente memoria di base, è possibile utilizzare un hash privo di errori per eliminare tutti gli accessi non necessari al disco; d'altra parte, con una memoria di memoria limitata, la tecnica di Bloom utilizza un'area di hash più piccola, ma elimina la maggior parte degli accessi non necessari. Ad esempio, un'area hash solo il 15% delle dimensioni necessarie per un hash ideale privo di errori elimina ancora l'85% degli accessi al disco. In generale, sono necessari meno di 10 bit per elemento per una probabilità di falsi positivi dell'1%, indipendente da la dimensione o il numero di elementi nel set.
Descrizione dell' algoritmo
Un filtro Bloom vuoto è un array bit di m bit, tutti impostati su 0. Ci devono anche essere k diverse funzioni hash definite, ognuna delle quali mappa o hash un elemento impostato su una delle posizioni m array, generando una distribuzione casuale uniforme. Tipicamente, k è una costante, molto più piccola di m, che è proporzionale al numero di elementi da aggiungere; la scelta precisa di k e la costante di proporzionalità di m sono determinate dal tasso falso positivo previsto del filtro.
