Φίλτρο Bloom
Ένα φίλτρο Bloom είναι μια δομή δεδομένων που επιτρέπει στους υπολογιστές να βλέπουν αν ένα δεδομένο στοιχείο εμφανίζεται σε ένα σύνολο. Τα φίλτρα Bloom χρησιμοποιούν συναρτήσεις κατακερματισμού για να το κάνουν αυτό. Για κάθε στοιχείο που προστίθεται, υπολογίζεται μια τιμή κατακερματισμού. Όταν προστίθεται ένα νέο στοιχείο, η τιμή κατακερματισμού του συγκρίνεται με εκείνη των άλλων στοιχείων του συνόλου. Ένα φίλτρο Bloom είναι μια πιθανοτική δομή δεδομένων. Είναι δυνατόν να έχουμε ψευδώς θετικό αποτέλεσμα, αλλά όχι ψευδώς αρνητικό. Με άλλα λόγια, ένα ερώτημα επιστρέφει είτε "ενδεχομένως στο σύνολο" είτε "σίγουρα όχι στο σύνολο". Στοιχεία μπορούν να προστεθούν στο σύνολο, αλλά όχι να αφαιρεθούν. Για κάθε προστιθέμενο στοιχείο, η πιθανότητα να λάβουμε ψευδώς θετικό αποτέλεσμα αυξάνεται.
Ο Edward Bloom πρότεινε το φίλτρο Bloom το 1970. Στο άρθρο του, ο Bloom υποθέτει ότι υπάρχει ένας αλγόριθμος για την παύλα των λέξεων στο τέλος μιας γραμμής. Σύμφωνα με το παράδειγμα, οι περισσότερες λέξεις έχουν απλά μοτίβα παύλας. Αλλά περίπου το 10% των λέξεων απαιτούν χρονοβόρες αναζητήσεις για να βρουν τον σωστό κανόνα. Η περίπτωσή του ήταν αυτή της παύλασης περίπου 500.000 λέξεων. Είδε ότι χρησιμοποιώντας τις "κανονικές" τεχνικές κατακερματισμού χωρίς λάθη, αποθηκεύοντας τα μοτίβα παύλας, θα απαιτούσε πολλή μνήμη. Διαπίστωσε ότι χρησιμοποιώντας τη δική του τεχνική, μπορούσε να εξαλείψει τις περισσότερες αναζητήσεις. Για παράδειγμα, μια περιοχή κατακερματισμού μόνο το 15% του μεγέθους που χρειάζεται ένας ιδανικός κατακερματισμός χωρίς σφάλματα εξακολουθεί να εξαλείφει το 85% των προσπελάσεων στο δίσκο.
Γενικότερα, λιγότερα από 10 bits ανά στοιχείο απαιτούνται για 1% πιθανότητα ψευδώς θετικού αποτελέσματος, ανεξάρτητα από το μέγεθος ή τον αριθμό των στοιχείων του συνόλου.
Ερωτήσεις και απαντήσεις
Ερ: Τι είναι το φίλτρο Bloom;
A: Ένα φίλτρο Bloom είναι μια δομή δεδομένων που επιτρέπει στους υπολογιστές να δουν αν ένα δεδομένο στοιχείο εμφανίζεται σε ένα σύνολο. Χρησιμοποιεί συναρτήσεις κατακερματισμού για να το κάνει αυτό υπολογίζοντας την τιμή κατακερματισμού κάθε στοιχείου που προστίθεται και συγκρίνοντας την με τα άλλα στοιχεία του συνόλου.
Ερ: Τι είδους δομή δεδομένων είναι ένα φίλτρο Bloom;
Α: Ένα φίλτρο Bloom είναι μια πιθανοτική δομή δεδομένων, που σημαίνει ότι υπάρχει πιθανότητα να έχουμε ψευδώς θετικά αποτελέσματα, αλλά όχι ψευδώς αρνητικά.
Ε: Ποιος πρότεινε το φίλτρο Bloom;
Α: Ο Edward Bloom πρότεινε το φίλτρο Bloom το 1970.
Ερ: Ποιο ήταν το παράδειγμα του Edward Bloom για τη χρήση της τεχνικής του;
Α: Το παράδειγμα του Edward ήταν η διασταύρωση περίπου 500.000 λέξεων- διαπίστωσε ότι χρησιμοποιώντας την τεχνική του, μπορούσε να εξαλείψει τις περισσότερες αναζητήσεις και να μειώσει τις προσπελάσεις στο δίσκο κατά 15%.
Ερ: Πόσα bits ανά στοιχείο απαιτούνται για πιθανότητα 1% ψευδώς θετική;
Α: Λιγότερα από 10 bits ανά στοιχείο απαιτούνται για 1% πιθανότητα ψευδώς θετικού αποτελέσματος, ανεξάρτητα από το μέγεθος ή τον αριθμό των στοιχείων του συνόλου.
Ε: Είναι δυνατή η αφαίρεση στοιχείων από ένα φίλτρο bloom αφού προστεθούν;
Α: Όχι, στοιχεία μπορούν μόνο να προστεθούν στο σύνολο αλλά όχι να αφαιρεθούν.
Ερ: Η προσθήκη περισσότερων στοιχείων αυξάνει ή μειώνει την πιθανότητα εμφάνισης ψευδώς θετικού αποτελέσματος;
Α: Η προσθήκη περισσότερων στοιχείων αυξάνει την πιθανότητα εμφάνισης ψευδώς θετικού αποτελέσματος.
