Quotient Filter: Cache-Friendly Approximate Membership

The problem: membership without storing the keys

Many systems must answer one question millions of times per second: is this key in my set? A database wants to skip reading an SST file that cannot contain a row; a web cache wants to know if a URL was ever stored; a network router wants to test an IP against a blocklist. Keeping the full key set in memory is too expensive, so we accept a small lie: an approximate membership query structure may occasionally say "present" for an absent key (a false positive), but it will never say "absent" for a present key (no false negatives).

The quotient filter, introduced by Michael Bender and colleagues in 2012, solves this while fixing three chronic weaknesses of the Bloom filter:

• Cache behavior — a Bloom lookup probes k pseudo-random bits, causing up to k cache misses per query.
• Deletability — you cannot delete from a plain Bloom filter without corrupting other keys.
• Mergeability & resizing — two Bloom filters only merge if identical in size and hash count; a quotient filter can be resized and merged cheaply.

How it works: quotienting and Robin Hood clustering

Hash each key to a p-bit fingerprint f. Split it into two parts: the top q bits are the quotient and the bottom r bits are the remainder. The quotient is the canonical slot in a table of 2^q slots; only the remainder is actually stored. This quotienting trick (Cleary, 1984) is lossless: slot index + stored remainder reconstruct the full fingerprint.

Collisions (two keys sharing a quotient) are resolved with linear probing plus Robin Hood hashing, which keeps remainders in sorted order within a run. Three metadata bits per slot track the structure:

• is_occupied — some key canonically hashes to this slot.
• is_continuation — this slot continues a run (not the first remainder).
• is_shifted — this remainder was pushed out of its canonical slot.

insert(key):
  f = hash(key)
  q = f >> r;  rem = f & ((1<<r)-1)
  if slot[q] empty and not occupied:
     slot[q]=rem; set is_occupied[q]; return
  set is_occupied[q]
  find run for quotient q (scan back to cluster start,
     walk forward counting occupied slots)
  insert rem in sorted order, shifting later
     remainders right; set is_continuation/is_shifted

A run is all remainders sharing one quotient; a cluster is a maximal chain of runs with no empty slot between them.

Complexity and a worked step trace

Space: each slot holds r remainder bits plus 3 metadata bits. With r = log₂(1/ε) chosen for target false-positive rate ε, the cost is about 2.125 + log₂(1/ε) bits per key at load factor α ≈ 0.9 (the 3 metadata bits amortize to ~2.125 over the extra slot capacity). At ε = 1% that is roughly 9 bits/key — a hair better than a Bloom filter's 1.44·log₂(1/ε) ≈ 9.6.

Time: insert, lookup, and delete are O(1) expected. The worst case is proportional to the length of the cluster you land in; for α < 1 the expected cluster length is O(1/(1−α)), and clusters stay short below α ≈ 0.75–0.9. The false-positive probability is ≈ 2^−r (bounded by α·2^−r).

r=3, table size 8. Insert keys with fingerprints:
  A -> q=2 rem=5 : slot2=5,        occ2=1
  B -> q=2 rem=1 : run at 2 = [1,5] (sorted), slot2=1 slot3=5(cont,shift)
  C -> q=3 rem=4 : occ3=1; slot3 taken by B, shift -> slot4=4(shift)
query(rem=1,q=2): scan run at 2 -> finds 1  => MAYBE present
query(rem=6,q=2): run at 2 = {1,5}, no 6 => DEFINITELY absent

Where it is used in real systems

Quotient filters and their descendants show up wherever Bloom filters strain under cache pressure or need deletion:

• LSM-tree databases — the rank-and-select quotient filter (RSQF) and the counting quotient filter (CQF, Pandey et al., 2017) back point-lookup filtering in write-heavy stores; RocksDB's ribbon/quotient-style filters and research forks use them to skip SST files with one cache miss.
• Bioinformatics — Squeakr and Mantis use the counting quotient filter to count and index k-mers across terabytes of sequencing data, exploiting the CQF's ability to store multiplicities, not just membership.
• Streaming / networking — deletable, resizable filters track active flows and sliding-window sets where a Bloom filter's inability to forget is disqualifying.
• Storage dedup and caches — the single-cache-line lookup and mergeability make quotient filters attractive for on-disk indexes that are periodically compacted and merged.

The CQF variant is notable for pairing membership with an approximate count using variable-length counter encodings inside the same runs.

Comparison to Bloom and cuckoo filters

All three are AMQ structures with no false negatives, but they trade off differently:

• vs. Bloom filter: the quotient filter uses one contiguous access instead of k scattered probes, supports deletion, resizing, and merging, and is marginally more space-efficient at practical ε. The Bloom filter is simpler and slightly faster to build when cache misses are cheap.
• vs. counting Bloom filter: counting Bloom filters gain deletion but at ~4× the space; the quotient filter deletes at no space penalty.
• vs. cuckoo filter: both store fingerprints and support deletion. Cuckoo filters use two candidate buckets (two cache lines) and can fail to insert near capacity, requiring a rebuild; quotient filters degrade gracefully as α → 1 but slow down. Cuckoo filters are often a touch smaller at low ε; quotient filters resize and merge more naturally.

The key structural distinction: Bloom spreads a key across the whole array; quotient and cuckoo filters localize a key's data, which is what unlocks deletion and cache-friendliness.

Pitfalls, failure modes, and significance

Load-factor cliff. Performance is excellent below α ≈ 0.75–0.9 but degrades sharply as slots fill: clusters coalesce, and a single insert may shift a long run. Sizing the table for expected load — and resizing before it saturates — is essential; unlike a hash map you cannot let it run to 100% full.

Metadata correctness. The three-bit invariant (is_occupied, is_continuation, is_shifted) is subtle: a buggy shift on insert or delete silently corrupts run boundaries and yields false negatives, breaking the core guarantee. Naive implementations also waste bandwidth reading metadata bit-by-bit — the RSQF fixes this with rank-and-select over packed metadata words.

• Fingerprint collisions set the false-positive floor at ≈ 2^−r; you cannot beat it by adding slots, only by widening the remainder.
• Deletion must re-sort and un-shift the run, or remainders drift out of Robin Hood order.
• Not thread-safe by default; concurrent variants need locking or lock-free care.

Significance: the quotient filter reframed AMQ design around the memory hierarchy, and its descendants (RSQF, CQF) are now standard tooling in modern databases and genomics.

Quotient filter vs. other approximate membership structures (ε = target false-positive rate)

Structure	Bits per key	Lookup cache misses	Delete / resize / merge
Bloom filter	1.44 · log2(1/ε) (~9.6 at ε=1%)	k random probes	No / no / no
Counting Bloom filter	~4× a Bloom filter	k random probes	Delete yes; resize no
Quotient filter	~2.125 + log2(1/ε) (~9 at ε=1%)	~1 (one cluster)	Yes / yes (resize) / yes
Cuckoo filter	~3 + log2(1/ε)	2 buckets	Delete yes; resize no
Rank-and-Select QF (RSQF)	~2.125 + log2(1/ε), packed	~1	Yes / yes / yes (fast)