Bloom Filter

Bloom filter is a compact, probabilistic bit-array data structure within computation and algorithms designed to test whether a query element x is a member of a finite set S ⊆ U drawn from a large universe U. Introduced by American computer scientist Burton Howard Bloom in 1970 to eliminate disk-bound dictionary lookups for hyphenation exceptions, a Bloom filter represents a set of n elements using an array of m bits—without storing the keys themselves—by mapping each element to k bit positions via k independent uniform hash functions.

By trading a bounded one-sided error for substantial memory compression within computational complexity theory, a Bloom filter ensures zero false negatives (if x ∈ S, a membership query always returns "present") while permitting a tunable false-positive probability ε (where an element y ∉ S is reported as "possibly present" because all k of its target bits were previously set to 1 by other inserted elements). Operating in O(k) constant time independent of the cardinality n of the stored set and requiring only ~9.58 bits per element for a 1% false-positive rate regardless of key length, Bloom filters are ubiquitous across distributed Log-Structured Merge-tree (LSM-tree) databases, network packet routers, and high-throughput bioinformatics k-mer indexing for succinct de Bruijn graph genome assembly.

Bit-Array Representation, Insertion, and Membership Queries

A standard Bloom filter consists of a bit array B[0 .. m − 1] of length m bits initialized to 0, together with k independent hash functions h₁, h₂, ..., h_k : U → {0, 1, ..., m − 1} that map each key in universe U uniformly across the m array indices:

1. Insertion: To insert an element x ∈ S, evaluate all k hash functions and set each corresponding bit to 1:

B[h₁(x)] ← 1, B[h₂(x)] ← 1, ..., B[h_k(x)] ← 1.

1. Membership Query: To test whether query element y belongs to S, inspect the k bit positions B[h₁(y)], ..., B[h_k(y)]:
   • If any of the k bits equals 0 (B[h_i(y)] = 0 for some i), then y was never inserted (y ∉ S, zero false negatives).
   • If all k bits equal 1 (∏_i=1..k B[h_i(y)] = 1), the filter returns "possibly in S." Either y ∈ S (a true positive), or y ∉ S and all k of its bit positions were set to 1 by previously inserted elements (a false positive).

Analytical Derivation of the False-Positive Rate and Optimal k

Assume each hash evaluation h_i(x) selects one of the m bit positions independently and uniformly at random with probability 1/m. During a single hash evaluation, the probability that a specific bit B[j] is not set to 1 is 1 − 1/m. Because inserting n elements performs k · n independent hash evaluations in total, the probability p₀ that bit B[j] remains 0 after all n insertions is:

Consequently, the probability that a specific bit equals 1 after n insertions is 1 − p₀ ≈ 1 − e^−kn/m. For a query element y ∉ S, a false positive occurs when all k of its hashed locations contain 1s, giving the Bloom filter false-positive probability ε:

For a fixed bit-per-element allocation c = m/n, minimizing ε(k) = (1 − e^−k/c)^k is equivalent to minimizing its natural logarithm f(k) = k ln(1 − e^−k/c). Differentiating f(k) with respect to k and setting ∂f/∂k = 0 yields e^−k/c = 1/2, meaning that a Bloom filter achieves its minimum false-positive rate when 50% of the bits in the array are set to 1 (p₀ = 1/2), which maximizes the Shannon entropy of each bit in the array (H(1/2) = 1 bit). Solving e^−k/c = 1/2 gives the optimal number of hash functions:

Information-Theoretic Space Bounds and Double Hashing

Substituting k_opt = (m/n) ln 2 into ε ≈ (1/2)^{(m/n) ln 2} yields the required bit-per-element capacity:

Thus, a standard Bloom filter uses only 1 / ln 2 ≈ 1.4427 times the information-theoretic minimum memory log₂(1/ε) bits per element while supporting online insertions. Furthermore, Adam Kirsch and Michael Mitzenmacher (2008) proved that two independent hash functions g₁(x) and g₂(x) suffice to generate all k probe indices via linear combinations h_i(x) = (g₁(x) + i · g₂(x)) mod m with zero asymptotic increase in ε.

Deletion-Capable Variants: Counting, Cuckoo, and Xor Filters

A standard Bloom filter cannot delete elements because clearing any bit B[h_i(x)] ← 0 could erase a bit shared with another retained member z ∈ S. Three extensions address deletion and cache locality:

• Counting Bloom Filter (Fan et al., 2000): Replaces each bit with a 4-bit saturating counter C[j], incrementing on insertion and decrementing on deletion.
• Blocked Bloom Filter (Putze et al., 2009): Confines all k hash probes for an element within a single 512-bit CPU cache line, reducing memory access latency to 1 cache miss.
• Cuckoo Filter (Fan et al., 2014) and Xor Filter (Graf & Lemire, 2020): Store compact fingerprints in a cuckoo hash table (supporting O(1) deletion) or static GF(2) linear filter (~1.23 log₂(1/ε) bits per element).

LSM-Tree Storage Engines and Bioinformatics k-mer Assembly

In Log-Structured Merge-tree (LSM-tree) key-value databases (Google Bigtable, Apache Cassandra, RocksDB, LevelDB), attaching an in-memory Bloom filter (~10 bits/key, ε ≈ 0.8%) to each immutable on-disk Sorted String Table (SSTable) eliminates over 99% of disk seeks for absent keys. In bioinformatics, short-read DNA assemblers (ABySS, Minia, MEGAHIT) use counting and cascading Bloom filters to discard singleton sequencing-error k-mers and represent implicit de Bruijn graph vertices in ~4–12 bits per genomic k-mer, while Sequence Bloom Trees (Solomon & Kingsford, 2016) index thousands of RNA-seq experiments for rapid transcript search.

Why can a standard Bloom filter never produce a false negative?

When an element x is inserted, the bits at h₁(x), ..., h_k(x) are set to 1 and are never cleared back to 0. Any future query for x inspects those same k deterministic bit positions, all of which remain 1, so an inserted element is always recognized as present.

How can two Bloom filters be combined to represent the union or intersection of two sets?

For two Bloom filters B₁ and B₂ of equal length m using the same k hash functions, the bitwise OR (B₁ ∨ B₂) yields the filter for S₁ ∪ S₂, while the bitwise AND (B₁ ∧ B₂) approximates S₁ ∩ S₂ with zero false negatives. Set cardinality is estimated from the 1-bit count X via n̂ = −(m / k) ln(1 − X/m).

1. Bloom, B. H. (1970). "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM, 13(7), 422–426. https://doi.org/10.1145/362686.362692
2. Fan, L., Cao, P., Almeida, J., & Broder, A. Z. (2000). "Summary cache: a scalable wide-area Web cache sharing protocol." IEEE/ACM Transactions on Networking, 8(3), 281–293. https://doi.org/10.1109/90.851975
3. Kirsch, A., & Mitzenmacher, M. (2008). "Less hashing, same performance: Building a better Bloom filter." Random Structures & Algorithms, 33(2), 187–218. https://doi.org/10.1002/rsa.20208
4. Chikhi, R., & Rizk, G. (2013). "Space-efficient de Bruijn graph representation based on a Bloom filter." Algorithms for Molecular Biology, 8(1), 22. https://doi.org/10.1186/1748-7188-8-22
5. Solomon, B., & Kingsford, C. (2016). "Fast search of thousands of short-read sequencing experiments." Nature Biotechnology, 34(3), 300–302. https://doi.org/10.1038/nbt.3442