quotient-filter · research · also QF

Quotient filter

A quotient filter is an approximate membership structure that stores hash fingerprints using quotients, remainders and placement metadata.

The original design can enumerate fingerprints and merge compatible filters without fetching original keys. Resizing transfers a bit between quotient and remainder while preserving fingerprint width. [1]

Enumeration recovers fingerprints, not original keys. A positive lookup can be a collision; it is not an exact-key inventory. [1]

Relations

related
Bloom filter, VT-tree

Citations

  1. Bender et al. Don't Thrash: How to Cache Your Hash on Flash. PVLDB 5(11), 2012, pp. 1627-1637, section 3. (accessed 2026-11-10)

Further reading

  1. Hesela: VT-tree stitching and filter-maintenance costs (accessed 2026-11-10)
Sources & caveats
  • Describes the 2012 paper's quotient filter, not every later counting or concurrent variant. No implementation executed.

JSON: /data/terms/quotient-filter.json

Published by Hesela team · Updated

Report a correction · Editorial standards · Reuse guidance

Cite this page
Hesela team. Quotient filter. Hesela. 2026-11-10. https://hesela.dev/terms/quotient-filter/