Τι είναι ένα Bloom filter και ποια συμβιβασμό κάνει;

Question

Accepted Answer

Ένα **Bloom filter** είναι μια δομή δεδομένων **πιθανοθεωρητική** που εξοικονομεί χώρο και απαντά σε ερωτήματα συμμετοχής συνόλου με μια στροφή: μπορεί να έχει **ψευδώς θετικά** αλλά **ποτέ ψευδώς αρνητικά**. "Σίγουρα δεν υπάρχει" είναι σίγουρο· "πιθανώς υπάρχει" χρειάζεται έναν πραγματικό έλεγχο.

## Πώς λειτουργεί

Ένας πίνακας bit από `m` bits και `k` συναρτήσεις κατακερματισμού. Για να **προσθέσετε** ένα στοιχείο, ορίστε τα `k` bits στα οποία κατακερματίζεται. Για να **ερευνήσετε**, ελέγξτε εκείνα τα `k` bits — εάν κάποιο είναι 0, το στοιχείο είναι σίγουρα απών.

```text
bits: [0 0 0 0 0 0 0 0]
add "cat":  hash->bits 1,4,6  -> [0 1 0 0 1 0 1 0]
query "dog": hashes to 1,3,6 -> bit 3 is 0 -> DEFINITELY absent
query "cat": all of 1,4,6 set -> "probably present"
```

## Κώδικας

```python
class BloomFilter:
    def __init__(self, m, hashes):
        self.bits = [0]*m
        self.m, self.hashes = m, hashes   # list of hash fns
    def add(self, x):
        for h in self.hashes:
            self.bits[h(x) % self.m] = 1
    def __contains__(self, x):            # False = certain; True = maybe
        return all(self.bits[h(x) % self.m] for h in self.hashes)
```

| Λειτουργία | Χρόνος | Χώρος |
|---|---|---|
| add | O(k) | O(m) bits |
| query | O(k) | — |

Κανένα ψευδώς αρνητικά· το ποσοστό ψευδών θετικών πέφτει καθώς `m` (και ρυθμισμένα `k`) αυξάνονται.

## Συμβιβασμοί

- **Δυνάμεις:** ελάχιστο αποτύπωμα μνήμης έναντι αποθήκευσης πλήρων κλειδιών· λειτουργίες σε σταθερό χρόνο.
- **Αδυναμίες:** ψευδώς θετικά· **δεν μπορεί να διαγραφεί** (ένα τυπικό Bloom filter)· δεν μπορεί να απαριθμήσει τα μέλη.

## Γιατί έχει σημασία

Τα Bloom filters παρακάμπτουν φθηνά δαπανηρή εργασία: οι βάσεις δεδομένων (π.χ. Cassandra, HBase) τα χρησιμοποιούν για να αποφύγουν αναγνώσεις δίσκου για κλειδιά που **σίγουρα** δεν είναι στο δίσκο.

Εκπροσωπούν έναν κλασικό συμβιβασμό συστημάτων — αποδεχτείτε ένα μικρό, περιορισμένο ποσοστό σφάλματος σε ανταλλαγή για ένα τεράστιο μείωση της μνήμης και I/O.