Bloom Filters
Using probabilistic bit-arrays to check if an item is definitely absent, avoiding unnecessary disk reads.
What you'll learn
- Bit Array
- Hash Functions
- Probabilistic Return
TL;DR
Using probabilistic bit-arrays to check if an item is definitely absent, avoiding unnecessary disk reads.
Visual System Topology
Bloom Filter Bit Checking
If any bit is 0, item is definitely not in database. Avoids heavy disk read operations.
Concept Overview
A Bloom Filter is a highly space-efficient, probabilistic data structure used to check if an element is a member of a set, allowing for rapid lookups with zero false negatives but occasional false positives.
Key Architectural Pillars
Bit Array
A base-level array of m bits, all initially set to 0.
Hash Functions
k independent hash functions mapping input keys to specific bit positions.
Probabilistic Return
Lookup says either "Definitely Not in Set" (100% true) or "Probably in Set" (with false-positive probability p).