Παράδειγμα Φίλτρων Bloom

Ένα Bloom φίλτρο είναι μια πιθανοκρατική δομή δεδομένων που ελέγχει γρήγορα και αποδοτικά εάν ένα στοιχείο μπορεί να ανήκει ή σίγουρα δεν ανήκει σε ένα σύνολο.

Χρησιμοποιεί ένα bit vector όπου k συναρτήσεις κατακερματισμού ρυθμίζουν bits σε 1 κατά την εισαγωγή στοιχείων.

Για τον έλεγχο συμμετοχής, οι ίδιες συναρτήσεις κατακερματισμού επαναλαμβάνονται και ελέγχεται εάν τα αντίστοιχα bits είναι 1· αν κάποιο bit είναι 0, το στοιχείο σίγουρα δεν υπάρχει, ενώ αν όλα είναι 1, μπορεί να υπάρχει.

Η πιθανότητα ψευδούς θετικού υπολογίζεται περίπου με τον τύπο (1 - e^{-kn/m})^k και εξαρτάται από τον αριθμό bits m, τον αριθμό hashes k και τα στοιχεία n.

Ο βέλτιστος αριθμός συναρτήσεων κατακερματισμού k δίνεται από τον τύπο k = (m/n) ln(2) για δεδομένα m και n.

Οι λειτουργίες εισαγωγής και ελέγχου συμμετοχής έχουν χρόνο εκτέλεσης O(k).

Για βελτιστοποίηση επιλέγονται γρήγορες μη κρυπτογραφικές συναρτήσεις κατακερματισμού όπως Murmur, xxHash και FNV.

Τα Bloom φίλτρα βρίσκουν εφαρμογή σε δίκτυα, βάσεις δεδομένων και βιοπληροφορική για γρήγορη δοκιμή συμμετοχής.