In the previous articles in this series, we saw Bloom Filter implementations that didn't allow removing values without later producing wrong answers. Here we'll see Counting Bloom Filters, which (with an important restriction) allow both adding and removing values.
Counting Bloom Filters
In the previous parts, we considered Standard Bloom Filters and Double Hashing Bloom Filters. We saw how to create, update, and search them, but eventually realized we couldn't remove values from the filter without causing "collateral damage" and making the filter produce wrong answers. In this part we'll show a variant, a Counting Bloom Filter, that (with an important restriction) allows both adding and removing values.
When we tried to remove a value from a Standard Bloom Filter, we found that we could reset a bit set by other additions. The solution we can consider - and let's just consider additions and searches for now - is:
- Instead of an array of booleans, we will work with an array of counters.
- When we add a value to the filter, we will increment the corresponding counters by one, as determined by the hash functions.
- When we search for a value, instead of checking for true bits, we check whether all the counters are nonzero.
Let's see how we'd implement this.
Sizing a Counting Bloom Filter
When sizing a CBF, there's an extra factor to consider. Since the CBF just differs from a BF because it has a count map instead of a bit map, determining the size of the bit map and the number of hash functions to use require exactly the same calculations; nothing new here. However, there's an extra detail: how large should the counts be, what's the maximum value we should expect?
To save memory, we want to use the smallest possible counters, in bits. However, we can't guarantee that, in some cases, the added values won't cause a counter to overflow. We will pick a size that keeps the overflow probability acceptably low, so we can basically ignore the issue.
The basic approach would start by observing that the average number of "hits" for a given slot is hn/b, where h, n, and b are as before: number of hashes, number of values to store, and size of the count map. To consider instead the maximum count gets into probabilistic arguments involving Poisson distributions, which we won't get into, but there are published results that show that for the sizing formulae we are using, 4-bit counters (counts 0 to 15) have a probability of overflow on the order of 10^(‑15); essentially ignorable. If you may have insertions with heavy duplication (same item inserted again and again) then 5‑6 bits (counts up to 31 or 63) are usually overkill.
Even so! How would you deal with a possible overflow? We'll leave that topic to question 11½–4, because the change isn't hard, and we'll focus on simpler logic.
Creating and Adding to a Counting Bloom Filter
We can start with the BF code. We just have to change how we create the filter and how we use it.
const newCountingBloomFilter = (n, eps = EPSILON) => {
const b = Math.ceil(-(n * Math.log(eps)) / LN2_SQ);
const h = Math.max(1, Math.round((b / n) * LN2));
return {
b,
h,
➊ count: new Array(b).fill(0)
};
};
const add = (filter, value) => {
for (const idx of getIndices(filter, value)) {
➋ filter.count[idx]++;
}
};
const find = (filter, value) =>
➌ getIndices(filter, value).every((idx) => filter.count[idx] > 0);
There are only three changes with regard to what we saw earlier. When we initialize the array ➊ we fill it with zeroes instead of false. On adding a value ➋ we increment the counter instead of setting it to true. Finally, when searching ➌ non-zero counts are equivalent to a set bit.
Going back to our BF example, Figure 11½–7 below shows how the counts would look after adding three of the Marx brothers.
Figure 11½–7: Three additions to a CBF, using a count map instead of a bit map
If you compare this with Figure 11½–2, the involved hash-calculated positions are the same, but now when two or more values hash to the same place, we increment the count instead of setting a bit.
Removing a value from a Counting Bloom Filter
Now we could implement a remove operation as follows - but there's a hidden potential issue!
const remove = (filter, value) => {
➊if (find(filter, value)) {
➋ for (const idx of getIndices(filter, value)) {
filter.count[idx]--;
}
}
};
The logic seems straightforward. We first check ➊ if the value is in the filter, and if so ➋ we decrement all its counters; what could go wrong? Remember that find may produce false positives; even if it returns true, the value may not have been added to the filter, and you would decrement counts for other values, even producing false negatives; bad!
For instance, we earlier saw that GUMMO produced a false positive. If we use the logic above, the resulting situation would be as shown in Figure 11½–8 below.
Figure 11½–8: Removing GUMMO, a false positive, generates a problem.
But what happens now if we search for CHICO, which we added to the filter? Figure 11½–9 shows that this produces a false negative; a no-no!
Figure 11½–9: After removing GUMMO we get a false negative for CHICO.
The issue is clear: as with a BF, we shouldn't remove a value unless we're sure it was added to the filter, and we can't rely on a find operation because it may produce false positives, as in the case we just showed.
This means we can use a CBF for removals only if we have a secondary way to ensure the value to be removed was actually inserted. This, of course, means the caller is responsible for keeping the structure healthy, and that's either a risk (if done wrongly) or a costly chore (if done rightly). Figure 11½–10 shows a possible flowchart.
Figure 11½–10: Using a secondary store for checks allows successful removals
With this approach, counts guarantee you never produce false negatives: adding a value increments some counts, removing that value decrements the same counts, and no other counts are affected.
A CBF is thus a first approximation to a Bloom Filter that allows removals, with high performance but a separate risk, or the need for a secondary test. We will move on to other implementations that may be costlier or more complicated but place fewer restrictions on users. Next, we'll consider the first option: Quotient Filters.
Bye for now! In the next article in the series, we will study Quotient Filters, which allow removals with fewer issues.
Questions
11½–4. Over the top? The usual solution to counter overflows is to check the count before adding a value; if it's already at the maximum, don't modify it. When removing a value, do a similar test, and if the count is at maximum, do not decrement it. (See the changed logic below.) What are the consequences of this logic in terms of false positives and false negatives?
const MAX_VALUE = 15; // 4-bit counters assumed
const add = (filter, value) => {
for (const idx of getIndices(filter, value)) {
if (filter.count[idx] < MAX_VALUE) {
filter.count[idx]++;
}
}
};
const remove = (filter, value) => {
if (find(filter, value)) {
for (const idx of getIndices(filter, value)) {
if (filter.count[idx] !== MAX_VALUE) {
filter.count[idx]--;
}
}
}
};
Top comments (0)