System Design Fundamentals

0% completed

​

Variants and Extensions of Bloom Filters

Here are a few variants and extensions of Bloom filters:

1. Counting Bloom Filters

Counting Bloom filters extend the standard Bloom filter by using an array of counters instead of a simple bit array. This modification allows for the deletion of elements from the filter, as each counter can be incremented or decremented when elements are added or removed, respectively. However, this added functionality comes at the cost of increased storage space and complexity.

.....

.....

.....

Like the course? Get enrolled and start learning!
Ayush Sur

Ayush Sur

· 2 months ago

Cuckoo Filter

  • Alternative to Bloom filter
  • Supports:
    • membership queries
    • efficient deletion
  • Based on Cuckoo Hashing

Core idea:

store small fingerprints instead of full items

Each item:

  • has a fingerprint
  • can stay in 2 possible buckets

Insertion:

  • place fingerprint in one bucket
  • if full:
    • kick existing fingerprint out
    • move kicked fingerprint to its alternate bucket
    • repeat (cuckoo kicking)

Lookup:

  • compute 2 candidate buckets
  • check whether fingerprint exists there

Deletion:

directly remove fingerprint

Advantages:

  • easy deletion
  • often more space efficient than Bloom filter at low false positive rates
  • fast lookups

Disadvantages:

  • insertion may fail when table highly full
  • may require resize/rebu
Show 1 reply