Bloom Filter

Bloom filters achieve dramatic memory savings compared to traditional hash tables or sets. A Bloom filter requires only a few bits per element, regardless of element size. For example, storing 1 million URLs with a 1% false positive rate requires approximately 1.14 MB of memory, whereas a hash set storing the full strings could consume 100+ MB. This efficiency comes from representing set membership through a bit array and k independent hash functions, where each element is mapped to k bit positions. The trade-off is the introduction of false positives—the filter may incorrectly report an element as present when it is not—but false negatives are impossible. This property makes Bloom filters ideal for pre-filtering operations where a definitive check can follow a positive result.

The false positive probability of a Bloom filter is mathematically predictable and tunable based on three parameters:

• m: the size of the bit array
• k: the number of hash functions
• n: the number of inserted elements

The optimal number of hash functions is given by k = (m/n) * ln(2), which minimizes the false positive rate for a given bit array size. The resulting probability is approximately p ≈ (0.6185)^(m/n). This allows engineers to design filters with precise guarantees—for instance, allocating 10 bits per element yields roughly a 1% false positive rate, while 20 bits per element drops it to approximately 0.001%. This controllability is critical for canonicalization systems where the cost of a false positive (e.g., incorrectly flagging a URL as already processed) must be balanced against memory constraints.

Bloom filters support set union operations when two filters share the same bit array size and hash functions. The union of two Bloom filters is computed by performing a bitwise OR across their bit arrays, producing a new filter that represents the combined set. This property enables distributed deduplication architectures where multiple workers independently build local filters and periodically merge them. However, intersection operations are not straightforward—a bitwise AND produces a filter that may have a higher false positive rate than either parent. In practice, union operations are commonly used in log-structured merge trees and distributed crawlers to consolidate canonical URL sets across shards without transmitting the full dataset.

Standard Bloom filters do not support element deletion because setting a bit to zero could inadvertently remove other elements that hash to the same position. To address this, Counting Bloom filters replace each bit with a small counter (typically 4 bits), incrementing on insertion and decrementing on deletion. This enables dynamic set membership at the cost of increased memory usage and a small risk of counter overflow. For canonicalization workflows where URLs may be deprecated or redirected, Counting Bloom filters provide the flexibility to remove stale entries. An alternative approach is the Cuckoo Filter, which supports deletion natively while offering better space efficiency for low false positive rates and supporting dynamic resizing.

When the number of elements to insert is unknown in advance, a Scalable Bloom Filter dynamically allocates additional Bloom filters as the set grows. Each successive filter is configured with a tighter false positive probability, ensuring the overall false positive rate remains bounded. The query process checks each constituent filter in sequence. This design is particularly valuable for streaming canonicalization where the total corpus size cannot be predetermined—such as processing an unbounded feed of crawled URLs. The logarithmic growth of memory allocation ensures that the amortized cost per insertion remains constant, making it suitable for long-running, always-on deduplication services.

Bloom filters serve as a critical pre-filtering layer in canonicalization and deduplication systems:

• URL deduplication: Web crawlers use Bloom filters to avoid re-crawling already-processed URLs, reducing crawl budget waste.
• Near-duplicate detection: Combined with Simhash or MinHash, Bloom filters accelerate the identification of candidate near-duplicate documents before expensive pairwise comparisons.
• Cache filtering: Content delivery networks use Bloom filters to determine if a resource is likely cached, avoiding expensive cache lookups for definitely-absent items.
• Log-structured storage: Databases like Apache Cassandra use Bloom filters to avoid unnecessary disk reads when checking if a row exists in a particular SSTable. In each case, the filter eliminates the vast majority of negative lookups, allowing the system to reserve expensive definitive checks for the small fraction of positive results.

The probability that a Bloom filter incorrectly reports an element as a member of the set when it is not. This rate is controllable and trades off against memory usage.

• A filter with 1% false positive rate and 10 million items uses roughly 11.5 MB of memory
• False negatives are impossible—a Bloom filter will never claim an inserted element is absent
• The rate increases as the filter fills; optimal sizing requires estimating cardinality upfront
• Formula: p ≈ (1 - e^(-kn/m))^k where k is hash functions, m is bits, n is elements

Bloom filters require k independent, uniformly distributed hash functions to map each element to k bit positions. Cryptographic hashes like MD5 are overkill; non-cryptographic alternatives excel.

• MurmurHash3 and xxHash are preferred for their speed and distribution properties
• Double hashing technique generates k hash values from only two base hashes: h(i) = h1(x) + i * h2(x) mod m
• Poor hash functions with clustering cause premature saturation and elevated false positive rates
• Kirsch-Mitzenmacher optimization proves two hashes suffice without sacrificing uniformity

A variant that replaces each bit with a small n-bit counter, enabling element deletion—a capability standard Bloom filters lack. Increments on insertion, decrements on removal.

• A 4-bit counter per slot handles up to 15 collisions before overflow risk
• Memory footprint is 4x larger than an equivalent standard Bloom filter
• Overflow can be mitigated by switching to a d-left counting approach or using larger counters
• Critical for dynamic datasets where elements expire, such as cache eviction policies and network flow tracking

A dynamic variant that grows gracefully by adding new sub-filters when the current one reaches capacity, eliminating the need to pre-allocate for unknown cardinalities.

• Each successive sub-filter uses a tighter false positive probability to maintain a bounded cumulative rate
• Geometric series of probabilities: p * r^0, p * r^1, p * r^2... where r < 1
• Query checks all sub-filters; insertion only targets the active one
• Used in Apache Cassandra and RocksDB for unbounded datasets where pre-sizing is impractical

A Bloom filter alternative that supports deletion and higher lookup performance by storing fingerprints in a cuckoo hash table. Outperforms Bloom filters at low false positive rates.

• Stores short fingerprints rather than setting bits, enabling O(1) deletion without counters
• Uses partial-key cuckoo hashing: given a fingerprint and bucket index, the alternate bucket is computable
• Higher space efficiency than Bloom filters for false positive rates below 3%
• Implemented in RedisBloom and networking hardware for packet deduplication

Bloom filters support set union by bitwise OR of two filters of identical size and hash configuration. The result approximates the union of the two original sets.

• Union: BF(A ∪ B) = BF(A) | BF(B)—exact and lossless
• Intersection: bitwise AND produces a filter that may underestimate the true intersection due to collisions
• Useful for distributed aggregation: merge filters from sharded databases before querying
• Bloom join algorithms in distributed databases use this property to reduce network shuffle volume