Quotient Filter

Quotient Filter is a space-efficient, cache-local probabilistic data structure in computation and algorithms that answers approximate set-membership queries over a dynamic set S with zero false negatives and a tunable false-positive probability ε ≈ 2^−r. Introduced by Michael A. Bender, Martin Farach-Colton, Rob Johnson, Russell Kraner, Bradley C. Kuszmaul, Dzejla Medjedovic, Pablo Montes, Pradeep Shetty, Richard P. Spillane, and Erez Zadok in 2012—building on Donald Knuth's 1973 exercise on quotienting in The Art of Computer Programming and Cleary's 1984 compact hash tables—a quotient filter stores p-bit fingerprints inside an open-addressed linear-probing hash table of m = 2^q slots by implicitly encoding the high-order q bits in the slot address and storing only the low-order r = p − q remainder bits alongside 3 structural metadata bits per slot.

In computational complexity theory and external-memory database indexing, a classical Bloom filter issues k independent random bit probes across the entire array for every lookup or insertion, incurring up to k CPU cache misses or flash-storage page reads, and neither supports deletions nor allows resizing without re-hashing the original keys. Because a quotient filter stores full p-bit fingerprints in sorted canonical order across contiguous linear-probing clusters, every lookup, insertion, and deletion accesses at most one or two contiguous CPU cache lines, supports dynamic deletions without false negatives, and enables linear-time merging and doubling/halving of filter capacity without re-accessing the original keys.

Fingerprint Quotienting into q Quotient Bits and r Remainder Bits

Let S ⊆ U be a dynamic set of n elements, and let h : U → {0, 1}^p be a uniform hash function that maps each key x ∈ U to a p-bit fingerprint f = h(x). In a table of m = 2^q buckets, quotienting partitions the p-bit fingerprint f into two bit fields:

1. The Quotient f_q (High-Order q Bits): f_q = ⌊f / 2^r⌋ ∈ {0, 1, ..., 2^q − 1}, which designates the element's canonical slot (home bucket) in the array T[0 .. 2^q − 1].
2. The Remainder f_r (Low-Order r Bits): f_r = f mod 2^r ∈ {0, 1, ..., 2^r − 1}, where r = p − q. Only the r-bit remainder f_r is stored inside the slot array.

If a remainder f_r always resided at its canonical slot f_q, the complete p-bit fingerprint could be reconstructed losslessly via the identity f = (f_q ≪ r) | f_r. When multiple keys share the same quotient f_q (a quotient collision) or are displaced by earlier collisions under linear probing, a remainder f_r is shifted to a later slot s ≥ f_q (modulo 2^q).

Three Metadata Bits: is-occupied, is-continuation, and is-shifted

To reconstruct the original canonical quotient f_q of every stored remainder despite linear-probing shifts, a quotient filter maintains two ordering invariants: all remainders sharing the same quotient f_q are stored contiguously in ascending remainder order in a run, and the runs themselves appear in ascending order of their canonical quotients f_q. Each slot s ∈ {0, ..., 2^q − 1} carries 3 metadata bits alongside its r-bit remainder slot:

• *is-occupied*[s]: Set to 1 if and only if there exists at least one stored fingerprint in the filter whose canonical quotient equals s (f_q = s), regardless of whether that run is currently stored at slot s or has been shifted rightward to a later slot.
• *is-continuation*[s]: Set to 1 if and only if slot s holds a remainder that belongs to the same run (same canonical quotient f_q) as the remainder in the directly preceding slot s − 1. Consequently, *is-continuation*[s] = 0 marks the start of a new run (if slot s is non-empty).
• *is-shifted*[s]: Set to 1 if and only if the remainder stored in slot s does not reside at its canonical slot (s ≠ f_q).

Together, these three bits define the structural hierarchy of runs and clusters:

• A run is a contiguous block of slots storing all remainders that share a single canonical quotient f_q; its first slot has is-continuation = 0 and all subsequent slots in the run have is-continuation = 1.
• A cluster is a maximal contiguous sequence of occupied slots beginning at an anchor slot s₀ that holds an unshifted run-start (*is-occupied*[s₀] = 1, *is-continuation*[s₀] = 0, *is-shifted*[s₀] = 0) and continuing through all directly following slots that have is-shifted = 1.

Cluster Scanning and Membership Query Algorithm

To test whether a key x with fingerprint f = (f_q, f_r) is present in a quotient filter:

1. Fast Rejection: Inspect *is-occupied*[f_q]. If *is-occupied*[f_q] == 0, no element with quotient f_q is stored in the filter; return false in a single memory read.
2. Walk Backward to Cluster Anchor: Starting at s ← f_q, walk leftward (s ← s − 1) while *is-shifted*[s] == 1. During this backward scan, count the number c of slots encountered that have *is-occupied*[s] == 1. The scan stops at the cluster anchor s₀ where *is-shifted*[s₀] == 0.
3. Walk Forward to Target Run: Because runs occur in the same order as the is-occupied = 1 bits inside the cluster, advance s rightward from s₀ until c run starts (*is-continuation*[s] == 0) have been passed. Slot s now points to the start of the run for quotient f_q.
4. Scan Target Run: Compare f_r against the remainders in the run (while is-continuation == 1 in subsequent slots). Because remainders within a run are sorted in ascending order, stop as soon as a remainder ≥ f_r is seen or the run ends.

When the load factor α = n / 2^q is bounded away from 1 (e.g., α ≤ 0.75), standard linear-probing analysis by Knuth shows that the expected cluster length is O(1 / (1 − α)²) = O(1) slots (typically 2 to 6 slots), so the entire backward and forward walk executes inside a single 64-byte CPU cache line.

Dynamic Deletions and Keyless Resizing / Merging

Unlike a Bloom filter, deleting a fingerprint (f_q, f_r) from a quotient filter simply removes f_r from its run, shifts subsequent remainders in the same cluster leftward by one slot (clearing is-shifted on any run that returns to its canonical home slot), and clears *is-occupied*[f_q] ← 0 if the deleted remainder was the sole member of its run.

Furthermore, because every p-bit fingerprint f = (f_q ≪ r) | f_r can be reconstructed sequentially by streaming through the table in O(2^q) time, two quotient filters QF₁ and QF₂ can be merged in a single sequential pass (identical to merging two sorted arrays in merge sort), or doubled in capacity (q′ = q + 1, r′ = r − 1) by moving the most significant bit of each remainder f_r into the least significant bit of its quotient f_q without storing or re-hashing the original keys.

In 2017, Prashant Pandey, Michael A. Bender, Rob Johnson, and Rob Patro introduced the Rank-and-Select Quotient Filter (RSQF) and Counting Quotient Filter (CQF). Instead of walking backward across long clusters at high load factors (α = 90%–95%), RSQF organizes the table into 64-slot blocks aligned to 64-byte cache lines and stores two 64-bit metadata bitmaps per block: occupieds and runends (reducing metadata overhead from 3 bits to 2.125 bits per slot, including block offset counters).

Using x86 hardware bit-manipulation instructions (POPCNT for rank and BMI2 PDEP / TZCNT for select), RSQF locates the precise slot where the run for quotient f_q ends in O(1) constant instruction cycles even at 95% occupancy:

The Counting Quotient Filter (CQF) further encodes variable-length multiplicity counters directly inside each run using empty remainder slots when an item appears multiple times, outperforming the Count–Min sketch on skewed Zipfian distributions in network telemetry and bioinformatics k-mer counting (Squeakr) alongside de Bruijn graph assembly indexes.

How can a quotient filter double its capacity without re-hashing the original keys?

Each stored entry in a quotient filter with parameters (q, r) implicitly preserves the full p-bit fingerprint f = (f_q ≪ r) | f_r, where p = q + r. To double the number of buckets from 2^q to 2^q+1, a single sequential scan extracts each (f_q, f_r) pair, shifts the top bit of the remainder f_r into the bottom bit of the new (q + 1)-bit quotient, and writes the remaining (r − 1)-bit remainder into the new table in sorted order.

Why does a Quotient Filter outperform a Bloom filter on SSD and NVMe flash storage?

In a flash-backed storage engine (such as a B^ε-tree or LSM-tree), merging two SSTable runs with standard Bloom filters requires either keeping all raw keys to rebuild a larger Bloom filter or querying a stack of separate Bloom filters. Because quotient filters can be merged in a single sequential streaming pass over the filters alone, compaction never needs to re-hash keys or perform random I/O seeks.

1. Cleary, J. G. (1984). "Compact hash tables using bidirectional linear probing." IEEE Transactions on Computers, C-33(9), 828–834. https://doi.org/10.1109/TC.1984.1676499
2. Bender, M. A., Farach-Colton, M., Johnson, R., Kraner, R., Kuszmaul, B. C., Medjedovic, D., Montes, P., Shetty, P., Spillane, R. P., & Zadok, E. (2012). "Don't thrash: How to cache your hash on flash." Proceedings of the VLDB Endowment, 5(11), 1627–1637. https://doi.org/10.14778/2350229.2350275
3. Pandey, P., Bender, M. A., Johnson, R., & Patro, R. (2017). "A general-purpose counting filter: Making every bit count." Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD '17), 775–787. https://doi.org/10.1145/3035918.3035963
4. Pandey, P., Bender, M. A., Johnson, R., & Patro, R. (2018). "Squeakr: An precise and approximate k-mer counting system." Bioinformatics, 34(4), 568–575. https://doi.org/10.1093/bioinformatics/btx636
5. Conway, A., Farach-Colton, M., & Shilane, P. (2018). "Optimal hashing in external memory." Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs Vol. 107, 39:1–39:14. https://doi.org/10.4230/LIPIcs.ICALP.2018.39