Bloom Filters, Counting Bloom Filters, Cuckoo Filters & Xor Filters

Deriving the Optimal Bloom Filter Parameters ($m, n, k, \varepsilon$)

A standard Bloom filter consists of a bit array $B[0..m-1]$ initialized to $0$ and $k$ hash functions $h_1, \dots, h_k: \mathcal{U} \to \{0, \dots, m-1\}$. To insert $x$, set $B[h_i(x)] \gets 1$ for all $1 \le i \le k$. To query $q$, return PossiblyInSet iff $\bigwedge_{i=1}^k B[h_i(q)] == 1$; if any bit is $0$, $q$ is definitely not in the set.

After inserting $n$ elements, the probability that a specific bit remains $0$ is:

$$p_0 = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m}$$

The probability of a false positive for a query $q \notin S$ is the probability that all $k$ probed bits are $1$:

$$\varepsilon = (1 - p_0)^k \approx \left(1 - e^{-kn/m}\right)^k$$

Taking the derivative with respect to $k$ shows that $\varepsilon$ is minimized when exactly half the bits in the array are $1$ ($p_0 = 1/2$), giving the optimal hash count and bit budget:

$$k^* = \frac{m}{n} \ln 2 \approx 0.693 \frac{m}{n}, \qquad \frac{m}{n} = \frac{-\ln \varepsilon}{(\ln 2)^2} \approx 1.4427 \log_2\left(\frac{1}{\varepsilon}\right)\text{ bits/key}$$

Cuckoo Filters (Partial-Key Cuckoo Hashing) & Static Xor Filters

• Why You Cannot Naive-Clear Bits in a Bloom Filter: Clearing $B[h_i(x)] \gets 0$ on delete can clear a bit shared with another live key $y$, introducing illegal false negatives! Counting Bloom Filters replace each bit with a 4-bit saturating counter, but this $4\times$ memory bloat ($38.4$ bits/key at $\varepsilon = 1\%$) is prohibitive.
• Cuckoo Filters (Fan et al., 2014): Store only a short $f$-bit fingerprint $\text{fp}(x)$ inside a 4-slot-per-bucket Cuckoo table ($alpha = 0.95$). To relocate an existing fingerprint during Cuckoo eviction without having the original key $x$, Cuckoo Filters use Partial-Key Cuckoo Hashing:

  $$i_1 = h_1(x), \qquad i_2 = i_1 \oplus h_2(\text{fp}(x))$$

  Because XOR is its own inverse ($i_1 = i_2 \oplus h_2(\text{fp}(x))$), the alternate bucket $i_2$ can be computed purely from the current bucket index $i_1$ and the stored fingerprint $\text{fp}(x)$! Deletions simply remove one copy of $\text{fp}(x)$ from bucket $i_1$ or $i_2$.
• Xor Filters (Graf & Lemire, 2020): For immutable sets (such as LSM SSTables), an Xor Filter constructs an array $B$ of $m = \lfloor 1.23 n \rfloor + 32$ $f$-bit fingerprints via 3-hypergraph peeling so that for every key $x \in S$, $B[h_0(x)] \oplus B[h_1(x)] \oplus B[h_2(x)] == \text{fp}(x)$, achieving false positive rate $2^{-f}$ using only $1.23 f$ bits per key.

Visualizing Blocked Bloom Filters vs Cuckoo Fingerprint Duality

Production C++20 Implementation: Cache-Line Blocked Bloom Filter & Cuckoo Filter

// C++20: 64-Byte Cache-Line Blocked Bloom Filter (1 Cache Miss per Query)
#include <vector>
#include <array>
#include <cstdint>

class BlockedBloomFilter {
    struct alignas(64) CacheLineBlock {
        std::array<uint64_t, 8> words{}; // 512 bits = 64 bytes (1 L1 cache line)
    };

    std::vector<CacheLineBlock> blocks_;
    uint32_t k_;

    static uint64_t mix64(uint64_t x) noexcept {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

public:
    explicit BlockedBloomFilter(size_t numElements, uint32_t bitsPerKey = 10)
        : blocks_((numElements * bitsPerKey + 511) / 512),
          k_(static_cast<uint32_t>(bitsPerKey * 0.693147)) {
        if (blocks_.empty()) blocks_.resize(1);
        if (k_ < 1) k_ = 1;
    }

    void insert(uint64_t key) noexcept {
        uint64_t h = mix64(key);
        size_t blkIdx = ((h >> 32) * blocks_.size()) >> 32; // Lemire FastRange block select
        uint32_t h1 = static_cast<uint32_t>(h);
        uint32_t h2 = static_cast<uint32_t>(mix64(h));

        auto& blk = blocks_[blkIdx];
        for (uint32_t i = 0; i < k_; ++i) {
            uint32_t bit = (h1 + i * h2) & 511U;
            blk.words[bit >> 6] |= (1ULL << (bit & 63U));
        }
    }

    bool possiblyContains(uint64_t key) const noexcept {
        uint64_t h = mix64(key);
        size_t blkIdx = ((h >> 32) * blocks_.size()) >> 32;
        uint32_t h1 = static_cast<uint32_t>(h);
        uint32_t h2 = static_cast<uint32_t>(mix64(h));

        const auto& blk = blocks_[blkIdx];
        for (uint32_t i = 0; i < k_; ++i) {
            uint32_t bit = (h1 + i * h2) & 511U;
            if ((blk.words[bit >> 6] & (1ULL << (bit & 63U))) == 0) {
                return false; // 100% Guaranteed Negative!
            }
        }
        return true;
    }
};