jm + approximate   2

A general purpose counting filter
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!
cqf  counting-quotient-filters  data-structures  via:acolyer  coding  approximate  bloom-filters 
5 weeks ago by jm
Flower Filter
'A simple time-decaying approximate membership filter' -- like a Bloom filter with time decay. See also 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

Copy this bookmark: