Interview Bootcamp
Vote

0% completed

​

Variants and Extensions of Bloom Filters

The previous lesson listed what a standard Bloom filter cannot do: it cannot delete, it cannot grow, it cannot count, and it always costs the same memory. Each variant in this lesson removes one of those limits, and each one pays for it somewhere else.

1. Counting Bloom Filter

What changes. Every slot holds a small counter instead of a single bit. Adding an item increments the counters at its positions. Removing an item decrements them. A slot counts as "set" when its counter is above zero.

What it buys. Deletion

.....

.....

.....

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

Ayush Sur

· 3 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