Bloom-filtre er probabilistiske datastrukturer som brukes til å teste om et element er medlem av et sett. De er effektive når det gjelder plass og hastighet, noe som gjør dem egnet for applikasjoner der det kreves raske medlemsforespørsler med noen akseptable falske positive.

Hvordan Bloom Filtre fungerer

Et Bloom-filter bruker en bit- tabell og flere hash-funksjoner. Når et element er lagt til, kartlegger hvert hash-funksjon det til en posisjon i tabellen, angir de bitene til 1. For å sjekke om et element eksisterer, de samme hash-funksjonene brukes, og de tilsvarende bitene blir undersøkt. Hvis alle er satt til 1, er elementet sannsynligvis ikke i settet. Hvis noen er 0, er det definitivt ikke.

Beregninger for Bloom-filter

Den falske positive sannsynligheten avhenger av størrelsen på bitarrangen (m), antallet innsatte elementer (n) og antall hashfunksjoner (k). Sannsynligheten (p) til et falskt positivt kan tilnærmes ved:

p ⁇ (1 - e]-kn/m]]]]k

Optimale verdier for k og m kan minimere falske positiver for en gitt n. Typisk, k er valgt som:

k = (m/n) * SLUT 2]

Bruk tilfeller av Bloom-filter

Bloom-filtre brukes i ulike felt, inkludert:

  • Databasesystemer for rask medlemstesting
  • Web caching for å redusere diskoppslag
  • Distribuerte systemer for datasynkronisering
  • Nettverkssikkerhet for spamfiltrering

Begrensninger av Bloom-filter

Mens effektive, Bloom-filtre har begrensninger. De kan produsere falske positive, men ikke falske negative. Når bitene er satt til 1, kan de ikke tilbakestilles, noe som kan føre til unøyaktigheter over tid. De er heller ikke egnet til å slette individuelle elementer uten ekstra datastrukturer.