An XOR filter encodes set membership in a compact fingerprint table. For each key, three hash functions pick three table positions. The table is constructed so that XORing the three values at those positions yields the key's fingerprint. Querying is three lookups and two XORs.
Construction works by peeling a 3-uniform hypergraph. Each key is a hyperedge connecting its three hash positions. Find a position touched by exactly one key (degree 1), remove that key, repeat. If every key gets removed, fingerprints can be assigned in reverse order: each removed key's solo position is set to make the XOR equation hold. If peeling fails, rehash and retry.
Graf and Lemire introduced XOR filters in 2020, showing they use about 1.23x the theoretical minimum space (roughly 9.84 bits per element for 8-bit fingerprints). Binary Fuse Filters (Dietzfelbinger and Walzer, 2022) improve on this with a tapered table shape that reduces construction failure probability to near zero while matching the same space efficiency.
The peeling process is equivalent to solving a random system of linear equations over GF(2). When the hypergraph is sparse enough (table size around 1.23n), a random 3-uniform hypergraph is peelable with high probability. Watch the degree-1 vertices disappear one by one, then fingerprints fill in backwards.
Graf & Lemire (JEA 2020) / Binary Fuse Filters (2022) / Wikipedia