Xor filter

Deep dive

How it works

In: a key (hashed to 64 bits) · Out: "definitely absent" or "probably present" · State: a fingerprint array of 1.23·n + 32 slots, a seed (static after build) · Cost: query O(1), 3 independent reads; build O(n) expected

fp array: [ block 0 | block 1 | block 2 ]   each block = capacity/3 slots
key x:      h0(x)      h1(x)     h2(x)       fp[h0]^fp[h1]^fp[h2] == f(x)

1. Hash every key to 64 bits with a seed; derive h0, h1, h2 (one per block) and an f-bit fingerprint.
2. For each slot keep count and xor_of_hashes of the keys mapping to it.
3. Peel: push all slots with count 1 onto a queue. Pop slot i; if still count 1, its only key is xor_of_hashes[i]; push (i, key) on a stack and remove the key from its 3 slots (decrement counts, xor out), enqueueing slots that reach count 1.
4. If the stack holds all n keys, the system is solvable; else retry with a new seed.
5. Assign in reverse stack order: fp[i] = f(key) ^ fp[other1] ^ fp[other2]. The other slots are already final because they were peeled after i.

Code

fn fmix64(mut x: u64) -> u64 {
    x ^= x >> 33; x = x.wrapping_mul(0xFF51_AFD7_ED55_8CCD);
    x ^= x >> 33; x = x.wrapping_mul(0xC4CE_B9FE_1A85_EC53);
    x ^ (x >> 33)
}
fn reduce(x: u32, n: u32) -> u32 { ((x as u64 * n as u64) >> 32) as u32 } // [0, n) without division
fn fingerprint(h: u64) -> u8 { (h ^ (h >> 32)) as u8 }

pub struct Xor8 { seed: u64, block_len: u32, fp: Vec<u8> }

impl Xor8 {
    fn slots(&self, h: u64) -> [usize; 3] {
        let bl = self.block_len;
        [
            reduce(h as u32, bl) as usize,
            (reduce(h.rotate_left(21) as u32, bl) + bl) as usize,
            (reduce(h.rotate_left(42) as u32, bl) + 2 * bl) as usize,
        ]
    }

    pub fn contains(&self, key: u64) -> bool {
        let h = fmix64(key.wrapping_add(self.seed));
        let [a, b, c] = self.slots(h);
        fingerprint(h) == self.fp[a] ^ self.fp[b] ^ self.fp[c]
    }

    /// `keys` must be distinct (dedup first): equal keys can never be peeled.
    pub fn build(keys: &[u64]) -> Self {
        let cap = 32 + (1.23 * keys.len() as f64).ceil() as usize;
        let block_len = (cap / 3) as u32;
        let size = 3 * block_len as usize;
        let mut seed = 0x9E37_79B9_7F4A_7C15u64;
        for _attempt in 0..100 {
            let mut f = Xor8 { seed, block_len, fp: vec![0; size] };
            let mut count = vec![0u32; size];
            let mut xor = vec![0u64; size];
            for &k in keys {
                let h = fmix64(k.wrapping_add(seed));
                for s in f.slots(h) { count[s] += 1; xor[s] ^= h; }
            }
            let mut queue: Vec<usize> = (0..size).filter(|&i| count[i] == 1).collect();
            let mut stack: Vec<(usize, u64)> = Vec::with_capacity(keys.len());
            while let Some(i) = queue.pop() {
                if count[i] != 1 { continue; } // its key was already peeled via another slot
                let h = xor[i];
                stack.push((i, h));
                for s in f.slots(h) {
                    count[s] -= 1;
                    xor[s] ^= h;
                    if count[s] == 1 { queue.push(s); }
                }
            }
            if stack.len() == keys.len() {
                for &(i, h) in stack.iter().rev() {
                    let [a, b, c] = f.slots(h);
                    f.fp[i] = fingerprint(h) ^ f.fp[a] ^ f.fp[b] ^ f.fp[c]; // fp[i] is still 0 here
                }
                return f;
            }
            seed = fmix64(seed.wrapping_add(1)); // peeling failed: new hash functions
        }
        panic!("xor filter construction failed: duplicate keys?");
    }
}

Complexity and constants

• Bits/key: 1.23·f; FPR 2^-f. Xor8: 9.84 bits, 0.39 %; Xor16: 19.7 bits, 0.0015 %.
• Binary fuse 8-bit: about 9.0 bits/key (3-wise) or 8.6 (4-wise) at the same FPR.
• Peeling succeeds with high probability when slots ≥ 1.23·n (threshold of random 3-uniform hypergraphs ≈ 1.222). Expected attempts close to 1 for large n; small n needs the +32 slack.
• Query: 3 random reads; out of cache order of 100-150 ns total because they overlap, versus k dependent-ish probes for Bloom. In cache order of 5-10 ns.
• Build: memory-bound, order of 50-200 ns/key for xor filters; binary fuse builds faster because its slot windows are local.
• Temporary build memory: order of 30-40 bytes/key in this code (count, xor, queue, stack); the reference implementation packs it tighter.

Efficiency

• Cost: a query is 3 independent loads, branch-free: order of 5-10 ns in cache, order of 100-150 ns out of cache because the reads overlap. Memory is 1.23·f bits per key (9.84 bits at 0.39 % FPR with f = 8; binary fuse about 9.0 or 8.6). Build is memory-bound, order of 50-200 ns per key, with 30-40 bytes per key of temporary memory in the code above. Bound: memory latency.
• Levers:
  • binary fuse layout — 1.13× (3-wise) or 1.075× (4-wise) of the minimum instead of 1.23×, faster builds (Graf-Lemire 2022) — default over plain xor
  • 8- or 16-bit fingerprints — byte or halfword loads, no bit-unpacking — FPR of 0.39 % or 0.0015 %
  • pack count with xor, sort hashes by slot block — about half the build memory and better locality (reference C implementation) — large n
  • dedup keys before building — avoids failed peeling — inputs that may repeat
  • Ribbon filter instead — near-optimal space, tunable, at higher CPU cost (RocksDB) — memory matters more than speed
• Naive → standard → state of the art:
  • Bloom filter · 11.5 bits per key at 0.39 % FPR, k probes
  • xor filter · 9.84 bits per key, 3 reads
  • binary fuse filter · about 9.0 / 8.6 bits per key, 3 reads, local slot windows

Implementation notes

• Fingerprints of 8 or 16 bits keep queries to byte/halfword loads; arbitrary widths need bit-packing.
• Pack count into the low bits of xor (the C reference keeps a small count and the xor in one struct) to halve build memory.
• Sort or radix-partition hashes by slot block before building to improve locality on large n (binary fuse filters do this by design: all three slots fall in a narrow window).
• Persist seed, block_len, fingerprint width and hash algorithm with the array.
• For keys that are strings, hash to 64 bits once and dedup on the hash; 64-bit collisions among distinct keys are harmless except they appear as duplicates (dedup them).

Pitfalls

• Duplicate keys: construction never succeeds. Deduplicate (sort + dedup, or a hash set) first.
• Too few slots for small n: the +32 term matters below a few thousand keys.
• Trying to insert after build: impossible; rebuild or keep a small Bloom filter for the delta.
• Using a weak hash: correlated h0/h1/h2 make peeling fail repeatedly.

Variants and alternatives

In production

• Libraries: xor_singleheader (C, includes binary fuse), FastFilter (Java and C++), xorf (Rust), xorfilter (Go).
• Storage engines: static-filter niches are also served by Ribbon (RocksDB).
• No verified production deployment of xor or binary fuse filters outside these libraries was found, so no cross-field uses are listed.

Implementations

Sources

• Thomas Mueller Graf, Daniel Lemire, Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters, ACM Journal of Experimental Algorithmics 25, 2020. paper · arXiv · code
• Thomas Mueller Graf, Daniel Lemire, Binary Fuse Filters: Fast and Smaller Than Xor Filters, ACM Journal of Experimental Algorithmics 27, 2022. paper · arXiv
• Martin Dietzfelbinger, Rasmus Pagh, Succinct Data Structures for Retrieval and Approximate Membership, ICALP 2008.