Skip to main content
Definition Website Computer and Technology

Bloom Filter

Subject: Computer and Technology noun /ˈbluːm ˌfɪl.tər/ 1 definition

  1. Definition (noun)

    Entry #45 · Updated

    A Bloom Filter is a space-efficient probabilistic data structure used to test whether an element belongs to a set without storing the elements themselves. It pairs a fixed-length bit array initialized to zeros with multiple independent hash functions: inserting an item hashes it to several array positions and sets those bits to 1, while querying checks whether all of those positions are set. Because overlapping hashes from other entries can turn on every bit an unstored item maps to, a positive result means the element is only possibly in the set (a false positive), whereas encountering even a single 0 bit guarantees the element is definitely absent (zero false negatives). Standard implementations omit element deletion because clearing a shared bit could inadvertently invalidate other items, trading exactness and mutability for minimal memory overhead and fast pre-filtering ahead of costlier disk or network lookups.

    Common Types

    • Standard Bloom Filter: Uses a single fixed-size bit array and multiple hash functions for append-only membership queries with minimal memory overhead when element deletion is unnecessary.

    • Counting Bloom Filter: Replaces each single bit with a small multi-bit counter that increments on insertion and decrements on removal, enabling safe deletions at the cost of extra memory and potential counter overflow.

    • Scalable Bloom Filter: Dynamically allocates a sequence of bit arrays with progressively tighter false-positive bounds as earlier slices fill, supporting growing datasets whose final size is unknown upfront.

    • Blocked Bloom Filter: Partitions the bit array into CPU cache-line-sized blocks so all hash probes for an element fall within a single block, sacrificing slightly more space or false-positive tolerance for significantly higher cache locality and lookup throughput.

    Example

    A storage engine backed by multiple on-disk Sorted String Table (SSTable) files maintains an in-memory Bloom filter for each file's keys configured for a 1% false-positive rate. When a read request looks up a nonexistent key such as user:98421, the engine checks each filter in microseconds and skips disk reads for every file reporting the key as absent, incurring unnecessary disk I/O on at most about 1% of lookups.