Kaj je Bloomov filter in kakšno kompromiso naredi?

Question

Accepted Answer

**Bloomov filter** je prostor-učinkovita **verjetnostna** struktura, ki odgovori na vprašanje o pripadnosti množici z enim poudarkom: ima **lažno pozitivne rezultate**, vendar **nikoli lažno negativne**. "Zagotovo ni prisoten" je gotov; "možno je prisoten" zahteva pravo preverjanje.

## Kako deluje

Niz bitov dimenzije `m` bitov in `k` zgoščevalne funkcije. Za **dodajanje** elementa nastavite `k` bitov, na katere se zgoščuje. Za **poizvedbo** preverite tiste `k` bite — če je kateri koli 0, je element zagotovo odsoten.

```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"
```

## Koda

```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)
```

| Operacija | Čas | Prostor |
|---|---|---|
| add | O(k) | O(m) bitov |
| query | O(k) | — |

Ni lažno negativnih; stopnja lažno pozitivnih pada z `m` (in uglašenim `k`).

## Kompromisi

- **Prednosti:** majhen odtis pomnilnika v primerjavi z shranjevanjem polnih ključev; operacije v stalnem času.
- **Pomanjkljivosti:** lažno pozitivni; **ne morete brisati** (standardni Bloomov filter); ne morete našteti članov.

## Zakaj je važno

Bloomovi filtri poceni preskočijo drago delo: baze podatkov (npr. Cassandra, HBase) jih uporabljajo, da izognejo branju diska za ključe, ki **zagotovo** niso na disku.

Zastopajoče классičen kompromis sistemov — sprejmite majhno, omejeno stopnjo napake v zameno za ogromno zmanjšanje pomnilnika in I/O.