Counting Bloom Filter

A plain Bloom filter cannot forget. A counting Bloom filter (Fan, Cao, Almeida and Broder, 2000) replaces each bit with a small counter, so it can REMOVE a key. After this lesson your program increments and decrements counters, saturates them safely, and reports how often a key was added.

Counters instead of bits

ADD adds 1 to each of the key's k counters and CHECK asks whether they are all above 0. That is the same test as before, because a counter above 0 means "at least one key lit this position". REMOVE undoes an ADD by subtracting 1 from each counter. The counters are 4 bits wide, so they hold 0 to 15.

The positions of a key are a list of k numbers and can repeat (two of a key's hashes may land on the same counter). Treat the list as it is: ADD adds 1 once per entry, so a repeated position gets 2.

The rules

• ADD: for each position, counter = min(counter + 1, 15).
• REMOVE: if any of the key's counters is 0, the key cannot have been added: reply WAS_ABSENT and change nothing. Otherwise subtract 1 from each position's counter, except a counter that is 15 stays at 15, and a counter never goes below 0. Reply OK.
• CHECK: MAYBE if every counter is above 0, else NO.
• COUNT: the smallest of the key's counters.

A worked trace

With m = 10, k = 2: cat hashes to counters 9 and 7, dog to 3 and 9, so they share counter 9. Each line below prints the counters as one hex digit each:

command            counters       reply
INIT 10 2          0000000000
ADD cat            0000000101   OK
ADD dog            0001000102   OK
ADD cat            0001000203   OK
REMOVE cat         0001000102   OK
REMOVE cat         0001000001   OK
CHECK dog          0001000001   MAYBE

After ADD cat twice and ADD dog, the shared counter holds 3. Removing cat twice brings it to 1, and dog is still found because its other counter is untouched and the shared one is not zero. The next REMOVE cat would find a zero and answer WAS_ABSENT.

COUNT is an upper bound on how many times a key was added: other keys can only add to its counters, never subtract.

Saturation

A counter holds at most 15. If a 16th key lands on it, you must clamp, because wrapping to 0 would erase evidence of keys that are still present and create false negatives. Once a counter is saturated its true value is unknown, so REMOVE must leave it alone: decrementing it could make a present key disappear. The cost is a counter stuck at 15 forever. With sensible sizing this almost never happens (the original paper's analysis finds a counter reaching 16 vanishingly unlikely when k is chosen well), but adding one key 20 times is a cheap way to make it happen on purpose.

The hazard: removing what you never added

REMOVE only checks that the counters are non-zero. Those counters may be non-zero because of other keys. With m = 12, k = 2, after adding ant, bee, elk the counters read 110000002110. The key cow was never added, but every one of its counters is above 0, so REMOVE cow answers OK and subtracts from counters that belong to others. The counters become 100000002010, and now CHECK ant answers NO for a key that is really present: a false negative, the failure a Bloom filter exists to prevent. Only remove keys you know were added.

Cost

4-bit counters take 4 times the memory of a bit array with the same m. If you need deletes and can spare the space this is the simplest design. The Cuckoo filter (a later lesson) usually does better.

Common mistakes

• Wrapping a counter past 15 instead of clamping it.
• Decrementing a saturated counter, or letting a counter go below 0.
• Checking for zero after decrementing the first counter. Test all the counters first, then change any.
• Treating a repeated position as one: the list has k entries, and each entry counts.
• Calling COUNT a lower bound.

Your exercise

The starter already resets the table, answers CHECK and prints DUMP. You write ADD, REMOVE and COUNT.