Counting Quotient Filter

Overview

The Counting Quotient Filter (CQF) supports approximate membership testing and counts how often each item occurs in a dataset. Like a Bloom filter it can return false positives, but it is a general-purpose approximate membership query (AMQ) structure designed so that every bit counts.

The CQF is small and fast, has good locality of reference, and scales out of RAM to SSD. It supports deletions, counting (even on skewed datasets), resizing, merging, and highly concurrent access.

Key features

API and build

qf_insert(item, count);          // insert an item
qf_count_key_value(item);        // count (may over-count, like a Bloom filter)
qf_remove(item, count);          // decrement; count = 0 removes the item

$ make test && ./test 24 8       # Haswell or newer
$ make NH=1 test                 # older CPUs

Citation

@inproceedings{PandeyBJP17,
  author    = {Prashant Pandey and Michael A. Bender and Rob Johnson and Rob Patro},
  title     = {A General-Purpose Counting Filter: Making Every Bit Count},
  booktitle = {Proceedings of the 2017 ACM International Conference on Management of Data (SIGMOD)},
  pages     = {775--787},
  year      = {2017},
  doi       = {10.1145/3035918.3035963}
}