Come funzionano i filtri di fioritura scalabili?

Fammi provare a dare una possibilità per vedere quanto posso macellarlo. : -)

Quindi, per iniziare, devi essere in grado di creare un normale filtro di fioritura che permetta un numero finito di elementi con una probabilità massima di un falso positivo. L'aggiunta di queste funzionalità al filtro di base è necessaria prima di provare a realizzare un'implementazione scalabile.

Prima di provare a controllare e ottimizzare la probabilità, vediamo quale è la probabilità di una determinata dimensione del filtro di fioritura.

Per prima cosa dividiamo il campo di bit di quante funzioni di hash abbiamo (numero totale di bit / numero di funzioni hash = slice) per ottenere k fette di bit che rappresentano ciascuna funzione di hash in modo che ogni elemento sia sempre descritto da k bit.

Se aumenti il numero di fette o il numero di bit per fetta, la probabilità di falsi positivi diminuirà.

Ne consegue anche che quando vengono aggiunti degli elementi, più bit sono impostati su 1, quindi aumentano i falsi positivi. Ci riferiamo a questo come il "rapporto di riempimento" di ogni fetta.

Quando il filtro contiene una grande quantità di dati, possiamo supporre che la probabilità di falsi positivi per questo filtro sia il rapporto di riempimento elevato al numero di fette (se dovessimo effettivamente contare i bit invece di usare un rapporto, questo semplifica in una permutazione con problema di ripetizione).

Quindi, come possiamo capire come scegliere una probabilità di falsi positivi in un filtro di fioritura? Possiamo modificare il numero di sezioni (che influirà sul rapporto di riempimento).

Per capire quante fette dovremmo avere, iniziamo con il calcolo del rapporto di riempimento ottimale per una fetta. Poiché il rapporto di riempimento è determinato dal numero di bit in una sezione che sono 1 rispetto al numero di bit che sono 0, possiamo determinare che ciascun bit rimarrà non impostato con probabilità di (100% - (1 / bit in una sezione) ). Dal momento che verranno inseriti più elementi, abbiamo un'altra permutazione con problemi di reputazione e estendiamo le cose al rapporto di riempimento previsto, che è (100% - ((100% - (1 / bit in una sezione)) ^ "elementi inseriti")). Bene, si scopre che questo è molto simile ad un'altra equazione. Nella carta, mettono in relazione il rapporto di riempimento con un'altra equazione, quindi si adatta perfettamente a una serie di Taylor (1-e ^ (- n / m)). Dopo un po 'di futzing con questo, si scopre che il rapporto di riempimento ottimale è sempre di circa il 50%, indipendentemente dalle variabili che si modificano.

Quindi, poiché la probabilità di un filtro è il rapporto di riempimento elevato al numero di fette, possiamo riempire il 50% e ottenere P = (50%) ^ k o k = log_2 (1 / P). Possiamo quindi usare questa funzione per calcolare il numero di sezioni che dovremmo generare per un dato filtro nell'elenco dei filtri per un filtro di fioritura scalabile.

    def slices_count(false_positive_probability):
        return math.ceil(math.log(1 / false_positive_probability, 2))

Modifica: Dopo aver scritto questo, ho trovato una menzione della "regola del cinquanta per cento" durante la lettura sull'assegnazione dinamica della memoria basata su buddy system in TAoCP Vol 1, pp 442-445 con un ragionamento molto più pulito rispetto all'adattamento della curva a (1-e ^ (- n / m)). Knuth fa anche riferimento a un articolo "La regola del cinquanta percento rivisitata" con un po 'di background sul concetto ( pdf disponibile qui ).

Un elemento si trova nel filtro di fioritura scalabile se qualsiasi filtro restituisce true. Quindi, è possibile aggiungere filtri senza influire sulle query di appartenenza per gli elementi precedenti.

Per essere sicuro di avere una garanzia di falsi positivi nel caso peggiore, vengono aggiunti nuovi filtri con tassi di falsi positivi che diminuiscono geometricamente. Ad esempio, il primo filtro ha percentuale di falsi positivi p , il secondo rp , il terzo r^2p , ecc. La probabilità di un falso positivo sul filtro di generazione scalabile viene quindi limitata dal limite dell'unione: sum_{k>=0} r^k p = p/(1-r) .

I was reading up on scalable bloom filters and could not understand how each time a constituent bloom filters fills up, a new bloom filter with larger size is added.

The elements that contributed to the set bits in the initially created filters cannot be looked up for presence. Perhaps I am wrong in my understanding of this?

Ciao,
L'idea di base è quella di aggiungere al primo filtro fino a quando il campo di bit del filtro di primo livello non è saturo. Essere saturi significa non significa che ogni bit è usato, ma significa che il filtro contiene così tante voci che voci aggiuntive creerebbero troppi falsi positivi.

Dal punto di saturazione, qualsiasi nuovo elemento non verrà aggiunto al filtro saturo, ma a un sub-filtro nuovo e più grande (il filtro di secondo livello).

Per trovare un valore, dovresti cercare nel filtro di primo livello e, se non riesci a trovarlo lì, lo cercherai nel filtro di secondo livello. Se è possibile trovarlo in uno di questi filtri, è (con buone probabilità) "noto" al filtro (i falsi positivi possono verificarsi a causa della natura dei filtri Bloom). Se non riesci a trovare il valore in nessuno dei filtri, il filtro è garantito per non averlo visto. Questo, ovviamente, può essere espresso come una struttura dati ricorsiva.

Potresti leggere il mio post sul blog che contiene un'implementazione scalabile del filtro Bloom in Java e una spiegazione su come funziona in dettaglio.