**jm + approximate**
2

A general purpose counting filter

cqf
counting-quotient-filters
data-structures
via:acolyer
coding
approximate
bloom-filters

august 2017 by jm

This paper introduces a new AMQ data structure, a Counting Quotient Filter, which addresses all of these shortcomings and performs extremely well in both time and space: CQF performs in-memory inserts and queries up to an order of magnitude faster than the original quotient filter structure from which it takes its inspiration, several times faster than a Bloom filter, and similarly to a cuckoo filter. The CQF structure is comparable or more space efficient than all of them too. Moreover, CQF does all of this while supporting counting, outperforming all of the other forms in both dimensions even though they do not. In short, CQF is a big deal!

august 2017 by jm

Flower Filter

july 2013 by jm

'A simple time-decaying approximate membership filter' -- like a Bloom filter with time decay. See also http://eng.42go.com/flower-filter-an-update/ for some notes on the non-independence of survival probabilities, and how that imposes negligible differences in practice.

bloom-filter
algorithms
coding
probabilistic
approximate
time
decay
july 2013 by jm

**related tags**

Copy this bookmark: