hesela.devCounting quotient filter
A counting quotient filter is a quotient-filter variant that encodes fingerprint multiplicities with variable-sized counters and rank-and-select metadata.
The design packs counters into remainder slots rather than storing a separate copy for every duplicate. Its approximate counts can overestimate a key's true multiplicity when distinct keys share a fingerprint. [1]
With the tested default-hash mode, 5 copies of one key and 2 of a colliding key return 7 for either key, including after a resize. Deletion needs an exact outstanding-insertion history: a positive approximate count alone is insufficient. This is a deliberately selected native contract test, not a measured error rate. [3]
The pinned API also offers invertible hashing for an appropriately bounded key domain; that is a different contract from compressing arbitrary keys. [2]
The pinned qf_delete_key_value reads the approximate count and removes that whole fingerprint/value count. In default-hash mode this does not isolate one original key from another colliding key. Use a decrement bounded by the intended key's known outstanding insertions; this qualification is source-derived, not another native test. [2]
Relations
Citations
- Pandey, Bender, Johnson and Patro. A General-Purpose Counting Filter: Making Every Bit Count. SIGMOD 2017, 775-787, sections 3-4. DOI: 10.1145/3035918.3035963.
- CQF author implementation, commit 68939f587b0f33f8c45be4f0e2a18e12bffa9fa6: hash modes and update/query API.
- Hesela. Quotient filters: exact fingerprints, approximate keys. Native source checks and replay files.
Sources & caveats
- Paper mechanism and native author-library execution are distinguished; no throughput, persistence, concurrency or FPR benchmark.