Video: Bloom Filters 2024
Il cuore di molti algoritmi di streaming sono i filtri Bloom. Creato quasi 50 anni fa da Burton H. Bloom, in un periodo in cui l'informatica era ancora piuttosto giovane, l'intento originale del creatore di questo algoritmo era di scambiare spazio (memoria) e / o tempo (complessità) con quello che chiamava errori consentiti. Il suo documento originale è intitolato Complessioni spazio / tempo nella codifica hash con errori consentiti.
Potresti chiederti dello spazio e del tempo che Bloom considera motivatori per il suo algoritmo. Immagina di dover determinare se un elemento è già apparso in uno stream utilizzando una struttura di dati precedentemente discussa. Trovare qualcosa in un flusso implica che la registrazione e la ricerca siano veloci, quindi una tabella hash sembra una scelta ideale. Le tabelle hash richiedono semplicemente di aggiungere gli elementi che si desidera registrare e archiviarli. Recuperare un elemento da una tabella hash è veloce perché la tabella hash utilizza i valori facilmente manipolati per rappresentare l'elemento, piuttosto che l'elemento stesso (che potrebbe essere piuttosto complesso). Tuttavia, la memorizzazione di entrambi gli elementi e un indice di tali elementi presenta limitazioni. Se una tabella hash ha più elementi di quanti ne possa gestire, come gli elementi in un flusso continuo e potenzialmente infinito, a un certo punto finirai per incorrere in problemi di memoria.
Una considerazione essenziale per i filtri Bloom è che possono verificarsi falsi positivi, ma i falsi negativi non possono. Ad esempio, un flusso di dati potrebbe contenere dati di monitoraggio in tempo reale per una centrale elettrica. Quando si utilizza un filtro Bloom, l'analisi del flusso di dati mostrerebbe che le letture previste sono probabilmente parte dell'insieme di letture consentite, con alcuni errori consentiti. Tuttavia, quando si verifica un errore nel sistema, la stessa analisi mostra che le letture non fanno parte dell'insieme delle letture consentite. È improbabile che i falsi positivi causino problemi, ma l'assenza di falsi negativi significa che tutti restano al sicuro. A causa del potenziale di falsi positivi, i filtri come il filtro Bloom sono strutture dati probabilistiche, che non forniscono una risposta certa ma probabile.
Gli hash, le singole voci in una tabella hash, sono veloci perché si comportano come l'indice di un libro. Si utilizza una funzione di hash per produrre l'hash; l'input è un elemento contenente dati complessi e l'output è un numero semplice che funge da indice per quell'elemento. Una funzione di hash è deterministica perché produce lo stesso numero ogni volta che lo si alimenta con uno specifico input di dati.Usi l'hash per localizzare le complesse informazioni di cui hai bisogno. I filtri Bloom sono utili perché sono un modo parsimonioso per registrare tracce di molti elementi senza doverli archiviare come fa una tabella hash. Funzionano in modo semplice e usano i seguenti ingredienti principali:
- Un vettore di bit: Un elenco di elementi di bit, in cui ogni bit nell'elemento può avere un valore di 0 o 1. L'elenco è lungo numero di bit chiamati m. La m maggiore è, meglio è, anche se ci sono modi per definire in modo ottimale le sue dimensioni.
- Una serie di funzioni hash: Ogni funzione di hash rappresenta un valore diverso. Le funzioni di hash possono scricchiare rapidamente i dati e produrre risultati uniformemente distribuiti, che sono risultati che vanno ugualmente dal minimo al massimo dei valori di uscita dell'hash.
