Filtro Bloom
Un filtro Bloom è una struttura di dati che permette ai computer di vedere se un dato elemento è presente in un set. I filtri Bloom utilizzano funzioni hash per fare questo. Per ogni elemento che viene aggiunto, viene calcolato un valore di hash. Quando un nuovo elemento viene aggiunto, il suo valore di hash viene confrontato con quello degli altri elementi dell'insieme. Un filtro Bloom è una struttura di dati probabilistica. È possibile ottenere un falso positivo, ma non un falso negativo. In altre parole, una query restituisce "possibilmente nell'insieme" o "decisamente non nell'insieme". Gli elementi possono essere aggiunti al set, ma non rimossi. Per ogni elemento aggiunto, la probabilità di ottenere un falso positivo cresce.
Edward Bloom propose il filtro Bloom nel 1970. Nell'articolo, Bloom suppone che ci sia un algoritmo per sillabare le parole alla fine di una riga. Secondo l'esempio, la maggior parte delle parole ha un semplice schema di sillabazione. Ma circa il 10% delle parole richiede un lungo lavoro di ricerca per trovare la regola corretta. Il suo caso è stato quello della sillabazione di circa 500.000 parole. Egli ha visto che l'uso delle "normali" tecniche di hashing senza errori, memorizzando gli schemi di sillabazione, avrebbe richiesto molta memoria. Scoprì che usando la sua tecnica, poteva eliminare la maggior parte delle ricerche. Per esempio, un'area di hash solo il 15% della dimensione necessaria per un hash ideale senza errori elimina ancora l'85% degli accessi al disco.
Più in generale, sono necessari meno di 10 bit per elemento per una probabilità di falsi positivi dell'1%, indipendentemente dalle dimensioni o dal numero di elementi dell'insieme.
Domande e risposte
D: Che cos'è un filtro Bloom?
R: Un filtro Bloom è una struttura di dati che consente ai computer di verificare se un determinato elemento è presente in un insieme. Utilizza le funzioni hash per farlo, calcolando il valore hash di ogni elemento aggiunto e confrontandolo con gli altri elementi dell'insieme.
D: Che tipo di struttura dati è un filtro Bloom?
R: Un filtro Bloom è una struttura di dati probabilistica, il che significa che esiste la possibilità di ottenere falsi positivi ma non falsi negativi.
D: Chi ha proposto il filtro Bloom?
R: Edward Bloom ha proposto il filtro Bloom nel 1970.
D: Qual era l'esempio di Edward per l'utilizzo della sua tecnica?
R: L'esempio di Edward era la sillabazione di circa 500.000 parole; ha scoperto che utilizzando la sua tecnica, poteva eliminare la maggior parte delle ricerche e ridurre gli accessi al disco del 15%.
D: Quanti bit per elemento sono necessari per una probabilità di falso positivo dell'1%?
R: Per ottenere l'1% di probabilità di falso positivo sono necessari meno di 10 bit per elemento, indipendentemente dalle dimensioni o dal numero di elementi dell'insieme.
D: È possibile rimuovere gli elementi da un filtro bloom una volta che sono stati aggiunti?
R: No, gli elementi possono essere solo aggiunti all'insieme, ma non rimossi.
D: L'aggiunta di più elementi aumenta o diminuisce la probabilità di ottenere un risultato falso positivo?
R: L'aggiunta di più elementi aumenta la probabilità di ottenere un risultato falso positivo.
