Bloom Filters

• Variable capacity

  • Easy to adjust
  • Page when full

• Fixed structure size

  • Uses 2n bit array
  • Initialized to zeros

• Insertion is easy

  • Use n-bit digest as indices into bit array

1

n bits

2n

bits

H(P)

Previous slide

Next slide

Back to first slide

View graphic version