search

splatlab / cqf

A General-Purpose Counting Filter: Counting Quotient Filter
BSD 3-Clause "New" or "Revised" License
125 stars 34 forks source link

Expected space/time? #1

Closed dnbaker closed 7 years ago

dnbaker commented 7 years ago

Very exciting work!

In comparing the Counting Quotient Filter to counting bloom filters and other probabilistic data structures, can you provide any numbers?

For example, the Cuckoo Filter paper (Table 1) lists the number of cache misses per lookup and space requirements as compared to the basic Bloom Filter, as well as whether or not deletion is supported. Of course, your work is more comparable to only the counting Bloom filter. (And, perhaps, comparable to HyperLogLog, which, while not optimized for it, provides a AMQ interface with counting.)

Thanks!

prashantpandey commented 7 years ago

Hi Daniel,

Yeah, we have a paper to accepted in SIGMOD 2017. I will share the link once it's published. We have an exhaustive comparison against AMQs (Cuckoo filter, Bloom filter, Quotient filter) and Counting filters (Counting Bloom filter) in the paper.

Thanks Prashant

prashantpandey commented 7 years ago

Hi Daniel,

Here is the paper: http://dl.acm.org/citation.cfm?id=3035963.