Counting Bloom filters: delete only a known insertion

Last updated: 7 Oct 20269 min read

tutorial

A counting Bloom filter substitutes counters for the bits of an ordinary Bloom filter. Each insertion increments several hash-selected positions; a query reports possible membership only when every selected counter is positive. A balanced removal decrements the same positions. It can therefore remove a known prior insertion without clearing a bit still needed by another item. This implementation accepts repeated insertions as separate multiplicities. The caller must know that an insertion exists and has not already been removed. A positive filter lookup is not evidence of that fact: an absent key can test positive through collisions, and deleting it can create a false negative for a real key. The filter deliberately stores no exact key ledger, so it cannot enforce the precondition by itself.

Operational case

An incident cache records pump-47 twice and valve-19 once. Removing one known pump insertion leaves pump-47 and valve-19 as possible members. The operation is safe because the caller has an exact insertion record elsewhere. A counter-underflow check catches some invalid removals, but it cannot detect every deletion of an absent false-positive key: the selected counters may all be positive due to other incidents. For a cache eviction pipeline, pair the filter with the authoritative cache-key state and update them as one logical mutation. Calling remove after a merely positive might-contain result breaks the no-false-negative contract.

Working Python program

import hashlib
from collections import Counter


class CountingIncidentFilter:
    def __init__(self, counter_count, hash_count):
        if counter_count < 1 or hash_count < 1:
            raise ValueError("counter and hash counts must be positive")
        self.counters = [0] * counter_count
        self.hash_count = hash_count

    def _positions(self, incident_id):
        encoded = incident_id.encode("utf-8")
        for hash_number in range(self.hash_count):
            digest = hashlib.blake2b(
                encoded + hash_number.to_bytes(4, "big"), digest_size=8
            ).digest()
            yield int.from_bytes(digest, "big") % len(self.counters)

    def add(self, incident_id):
        for position in self._positions(incident_id):
            self.counters[position] += 1

    def remove_known_insert(self, incident_id):
        positions = Counter(self._positions(incident_id))
        if any(self.counters[position] < multiplicity
               for position, multiplicity in positions.items()):
            raise ValueError("insufficient counters")
        for position, multiplicity in positions.items():
            self.counters[position] -= multiplicity

    def might_contain(self, incident_id):
        return all(self.counters[position] > 0
                   for position in self._positions(incident_id))


filter_index = CountingIncidentFilter(127, 4)
filter_index.add("pump-47")
filter_index.add("pump-47")
filter_index.add("valve-19")
filter_index.remove_known_insert("pump-47")
print("pump=", filter_index.might_contain("pump-47"),
      "valve=", filter_index.might_contain("valve-19"), sep="")

Output

pump=Truevalve=True

Time, space, and tradeoff

For H hash positions and M counters, insertion, lookup, and known-insert removal take O(H) hash and counter operations plus O(length of the encoded ID) hashing work per position. Storage is O(M) counters, larger than an M-bit filter; this Python list uses full integers and makes no compact-memory claim. Unbounded Python counters avoid arithmetic overflow, whereas fixed-width counters need an overflow strategy. Equal positions within one key are counted with multiplicity during removal. Hash collisions still permit false positives. The structure does not report exact multiplicity, retain item identities, or support untrusted deletion requests.

Common Mistakes

Do not delete a key merely because the filter says it might exist.
Do not ignore repeated hash positions when checking for counter underflow.
Do not claim the counter array stores exact key counts.
Do not let fixed-width counters silently wrap on overflow.

Connected lessons

Compare its mutation contract with Scalable Bloom filters: grow without discarding old members, Blocked Bloom filters: localize probes and watch skew, Cuckoo filters: relocate compact fingerprints safely, then run the membership audit and contract quiz.

Invertible Bloom tables: peel differences between replica ID sets examines a related structure with a different operation boundary.

data structures

range-query-structures