Quotient, Xor, Binary Fuse, and Ribbon Filters

In one line

Quotient filters store fingerprints in a compact open-addressed table (deletable, resizable, mergeable, cache-friendly). Xor and binary fuse filters (static sets) use ~1.23 and ~1.13 × log2(1/ε) bits per item with three lookups. Ribbon filters (RocksDB) give similar savings for static SST files.

0/6 · 0%

Think of it like this

Different filing systems. A quotient filter is a well-organised card index you can add to and remove from; an xor filter is a printed, laminated directory: smallest and fastest to look up, but you reprint it when anything changes.

Key ideas

01
Quotient filter (Bender et al., 2012): split a fingerprint into a quotient (slot index) and remainder (stored); collisions are handled by linear probing with 3 metadata bits per slot. Supports delete, resize (by rebuilding from fingerprints, without original keys), and merge; good locality. Uses somewhat more space than Bloom at moderate error rates and degrades above ~75–90% load.
02
Xor filter (Graf and Lemire, 2020): for a fixed set, build an array of fingerprints so that fp(x) = B[h0(x)] XOR B[h1(x)] XOR B[h2(x)]. ~1.23 × log2(1/ε) bits per item (~8.2 bits at 1%), 3 memory accesses, no deletes or inserts after construction.
03
Binary fuse filters (2022): a refinement to ~1.13 × log2(1/ε) bits per item and faster construction.
04
Ribbon filters (Dillinger and Walzer, 2021): solve a linear system over GF(2) to get near-optimal space (~30% smaller than Bloom in RocksDB) for static data like SST files, with slower construction.
05
When to use: static or rebuild-only sets (blocklists shipped to edge nodes, SST files) → xor, binary fuse or ribbon. Dynamic sets with deletes → cuckoo or quotient. Simplicity and incremental inserts → Bloom.

Code & diagrams

space.txttext

Bits per item for target error        1%      0.1%    Deletes  Dynamic inserts
Bloom (optimal k)                      9.6     14.4    no       yes
Blocked Bloom (approx)                 ~11     ~16     no       yes
Cuckoo (b=4, 95% load)                 10.1    13.6    yes      yes (can fail when full)
Quotient (~75% load)                   ~13     ~17     yes      yes (resizable)
Xor filter                             8.2     12.3    no       no (static)
Binary fuse filter                     ~7.5    ~11.3   no       no (static)
Ribbon (RocksDB)                       ~7      ~10.5   no       no (built per SST file)

Explain it without notes

Why are xor filters smaller than Bloom filters, and what do you give up?

Practice

Pick a structure for: (a) a 5-billion-entry blocklist shipped to edge servers daily, (b) a session filter with constant logins and logouts, (c) per-file filters in an LSM engine.

Trade-offs

↔
Static filters are smallest and fastest but must be rebuilt on change; dynamic ones accept updates at a space cost.

Done when you can

I can describe quotient, xor, binary fuse and ribbon filters and when each beats Bloom.