Xor Filter

Xor Filter is a fast, static probabilistic data structure in computation and algorithms that answers approximate set-membership queries over an immutable set S of n keys with zero false negatives and a configurable false-positive probability ε = 2^−L. Introduced by Thomas Mueller Graf and Daniel Lemire in 2020 as a specialization of the Chazelle–Kilian–Rubinfeld–Tal Bloomier filter (2004) and Dietzfelbinger–Pagh peelable hypergraph tables (2008), an Xor filter stores an array B[0 .. m − 1] of m ≈ ⌊1.23 n⌋ + 32 slots of L-bit values such that for every member key x ∈ S, the bitwise exclusive-OR (⊕) of three hashed array slots equals the L-bit fingerprint of x.

Within computational complexity theory and database storage engineering, classical Bloom filter arrays require m ≈ 1.4427 n log₂(1/ε) bits of memory and inspect k = ⌈0.693 (m/n)⌉ independent bit positions per lookup (e.g., k = 7 to 10 random memory probes for ε ∈ [0.1%, 1%]). When the key set S is immutable—as in flushed Sorted String Tables (SSTables) of Log-Structured Merge-tree (LSM) databases—the Xor filter reduces memory consumption to 1.23 n log₂(1/ε) bits (and 1.08 n log₂(1/ε) bits in the 4-wise Binary Fuse Filter generalization) while executing every membership query via 3 independent parallel memory loads and two bitwise XOR instructions, outperforming both standard and blocked Bloom filters in throughput and space efficiency.

The Bitwise XOR Membership Invariant

Let S ⊆ U be a static set of n distinct keys. Choose a fingerprint width L ≥ 1 bits (typically L = 8 or L = 16 bits, giving false-positive rate ε ≈ 2^−L = 1/256 ≈ 0.39% or 1/65,536 ≈ 0.00153%) and allocate an array B[0 .. m − 1] of m = ⌊1.23 n⌋ + 32 slots, partitioned into three contiguous segments of equal length s = m/3. Let fingerprint : U → {0, 1}^L be a uniform hash function mapping each key x to an L-bit integer, and let h₀, h₁, h₂ be three independent hash functions mapping x into the three respective segments of B:

During offline construction, the array B is populated so that every key x ∈ S satisfies the linear system equation over the finite vector space GF(2)^L:

Branch-Free Membership Lookup and False-Positive Probability

Once the array B is constructed, a membership query Contains(x) for any candidate key y ∈ U evaluates the single branch-free comparison:

Because the three array indices h₀(y), h₁(y), and h₂(y) depend only on the hash of y and have zero data dependency on one another, a superscalar CPU issues all three memory loads concurrently in a single instruction window:

1. Zero False Negatives: If y ∈ S, the construction invariant holds identically, so the three slots XOR to fingerprint(y) with probability 1.
2. False-Positive Rate ε = 2^−L: If y ∉ S, at least one of its three hashed positions (or their linear combination) behaves as an independent uniform L-bit word relative to fingerprint(y). Two independent L-bit words match across all L bits with probability:

Consequently, achieving a false-positive rate ε requires L = log₂(1/ε) bits per slot across m ≈ 1.23 n slots, yielding 1.23 log₂(1/ε) bits per key—within 23% of the Carter–Wegman (1978) information-theoretic lower bound of n log₂(1/ε) bits.

The 2-Core Phase Transition in Random 3-Partite Hypergraphs

At first glance, solving n linear equations B[h₀(x)] ⊕ B[h₁(x)] ⊕ B[h₂(x)] = fingerprint(x) in m variables via Gaussian elimination would require O(n³) time. Instead, Xor filters adopt the linear-time hypergraph peeling technique introduced by Majewski, Wormald, Havas, and Czech (1996) for minimal perfect hashing and analyzed by Molloy (2004).

Interpret the m array slots of B as vertices V = {0, 1, ..., m − 1} and each key x ∈ S as a 3-vertex hyperedge e(x) = {h₀(x), h₁(x), h₂(x)} in a random 3-partite 3-uniform hypergraph H = (V, E) with |V| = m and |E| = n. A hypergraph H is peelable (meaning its 2-core is empty) if one can repeatedly find a degree-1 vertex v ∈ V that belongs to only one remaining hyperedge e(x), remove (e(x), v) from H, and push (x, v) onto an ordering stack σ until no edges remain.

By random hypergraph theory, the threshold for the emergence of a non-empty 2-core in a 3-uniform hypergraph occurs at the threshold edge-to-vertex ratio:

Setting m = ⌊1.23 n⌋ + 32 places the hypergraph comfortably below the 2-core threshold, so hypergraph peeling succeeds on the first random hash seed with probability > 99.99% in linear O(n) time.

Two-Phase Peeling and Back-Substitution Algorithm

Construction proceeds in two linear O(n) passes without floating-point arithmetic or matrix inversion:

1. Forward Peeling Pass (Queue Scan): Count the incident degree deg[v] and the XOR sum of incident keys for each vertex v ∈ {0, ..., m − 1}. Push all vertices with deg[v] == 1 into a queue Q. While Q is non-empty, pop a degree-1 vertex v; if deg[v] is still 1, identify its unique remaining incident key x, push the pair (x, v) onto a stack S_order, and remove x from its other two vertices {u, w} = e(x) \ {v} (decrementing deg[u] and deg[w] and enqueueing either if its degree drops to 1).
2. Backward Assignment Pass (Stack Unwinding): Initialize B[0 .. m − 1] ← 0. Pop pairs (x, v) from S_order one by one. Because v had degree 1 when x was peeled, v has never been assigned or referenced by any previously popped key, and it will never be referenced by any subsequently popped key. Letting {u, w} = e(x) \ {v} be the other two vertices of x (which already hold finalized values), set:

By the self-inverse property of XOR (a ⊕ a = 0), this satisfies B[v] ⊕ B[u] ⊕ B[w] = fingerprint(x) while leaving all previously satisfied keys undisturbed.

In 2022, Thomas Mueller Graf and Daniel Lemire introduced the Binary Fuse Filter, improving on the Xor filter by constraining the three or four hashed vertices of each key x to fall within a localized sliding window of contiguous segments (inspired by Dietzfelbinger and Walzer's 2019 spatial coupling of peelable hypergraphs). Spatial coupling raises the hypergraph peeling threshold from 81.8% (m = 1.23 n) to 88.5% (m = 1.13 n) for 3-wise XOR and 92.6% (m = 1.079 n) for 4-wise XOR, while improving cache locality during both construction and querying.

In production storage engines such as Apache Cassandra, RocksDB, ClickHouse, Apache Parquet, and DuckDB, Xor and Binary Fuse filters replace per-SSTable and per-row-group Bloom filter blocks alongside HyperLogLog cardinality estimators and Count–Min sketch summaries, cutting filter RAM footprints by 20%–30% and doubling point-lookup filter throughput.

Why can an Xor filter not support dynamic insertions or deletions after construction?

In an Xor filter, each slot B[v] stores a coupled GF(2)^L linear combination shared across multiple keys whose hyperedges overlap at vertex v, solved in reverse peeling order. Modifying B[v] to insert or delete a key x after construction would alter the XOR sum for every other key y ∈ S whose hyperedge contains v, invalidating their membership invariants unless the affected hypergraph component is re-peeled.

Why does the Xor filter add a constant "+ 32" slots to the array size m = ⌊1.23 n⌋ + 32?

The asymptotic 3-uniform hypergraph peeling threshold m/n ≈ 1.2218 holds in the large-n limit (n → ∞), whereas for small sets (n < 1,000) finite-size fluctuations slightly increase the probability of a random 2-core cycle. Adding a tiny constant padding of 32 slots ensures that hypergraph peeling succeeds on the very first hash seed with probability > 99.9% even for small sets down to n = 10 keys.

1. Chazelle, B., Kilian, J., Rubinfeld, R., & Tal, A. (2004). "The Bloomier filter: An efficient data structure for static support lookup tables." Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '04), 30–39. https://doi.org/10.5555/982792.982797
2. Dietzfelbinger, M., & Pagh, R. (2008). "Succinct data structures for retrieval and approximate membership." Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008), LNCS Vol. 5125, 385–396. https://doi.org/10.1007/978-3-540-70575-8_32
3. Dietzfelbinger, M., & Walzer, S. (2019). "Dense peelable random uniform hypergraphs." Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), LIPIcs Vol. 144, 38:1–38:16. https://doi.org/10.4230/LIPIcs.ESA.2019.38
4. Graf, T. M., & Lemire, D. (2020). "Xor Filters: Faster and smaller than Bloom and Cuckoo filters." ACM Journal of Experimental Algorithmics, 25, 1.5:1–1.5:16. https://doi.org/10.1145/3376122
5. Graf, T. M., & Lemire, D. (2022). "Binary Fuse Filters: Fast and smaller than Xor Filters." ACM Journal of Experimental Algorithmics, 27, 1.5:1–1.5:15. https://doi.org/10.1145/3510449