Counting Bloom Filter: Deletion & Counter Overflow

Counter Width

2-bit (max 3)

4-bit (max 15)

8-bit (max 255)

Array size m 64

Hash functions k 3

Items

Live Stats

Items inserted

Load factor n·k/m

0.00

Theoretical FP rate

0.0%

Measured FP rate

0.0%

Overflow events

False negatives now

How it works

A counting Bloom filter (Fan, Cao, Almeida & Broder, 2000) replaces each of a plain Bloom filter's bits with a small fixed-width saturating counter, so items can be removed as well as inserted:

insert(x):  for i in 0..k-1: c[h_i(x) mod m] = min(c[...] + 1, MAXC)
delete(x):  for i in 0..k-1: c[h_i(x) mod m] = max(c[...] - 1, 0)
query(x):   all_i( c[h_i(x) mod m] > 0 )
MAXC = 2^bits - 1

The expected false-positive rate matches an ordinary Bloom filter with the same m, k, n:

P_fp ≈ (1 − e^(−kn/m))^k

The extra failure mode this simulator makes visible: once a counter reaches MAXC it stops incrementing — the increment is silently dropped ("overflow"). If several items collide on that saturated counter, deleting just one of them still decrements it once. Enough deletions can drive a saturated counter to 0 while other, still-present items that hash there are wrongly reported absent — a false negative, the price counting filters pay for supporting deletion. Narrower counters (2-bit, max 3) saturate almost immediately and make the bug easy to trigger; 8-bit counters make it vanishingly rare at normal load.

Insert / Delete / Query — apply the operation to the typed word using k independent hash positions.
Flood button — inserts 8 different words engineered to land in the same bucket set, so you can watch a narrow counter saturate and then read the false-negative counter climb as you delete them one by one.
Bar height & colour encode each counter's current value; a counter glowing red is at MAXC (saturated, losing information on the next insert).

Counter = 0 (empty) Counter mid-range Saturated (MAXC)

⚠ Couldn't load the 3D engineThree.js failed to load from the CDN. Check your connection and reload.