Scalable Bloom Filter

A Bloom filter must be sized for n keys before the first ADD. Guess too low and the error rate climbs; guess too high and you waste memory. A scalable Bloom filter (Almeida, Baquero, Preguica and Hutchison, 2007) removes the guess. After this lesson your program starts with a small filter and, when it fills, adds a bigger and stricter one.

The mechanism

The filter is a list of sub-filters, each an ordinary Bloom filter with its own m, k, capacity and error target.

• ADD goes to the newest sub-filter only. If the newest one already holds its full capacity, first allocate a new one: twice the capacity, half the error target, sized with the usual m/k formulas.
• CHECK must ask every sub-filter, newest to oldest, and answers MAYBE if any says MAYBE. An old key lives in an old sub-filter, so asking only the newest one loses it.

Why the error target must shrink

Each sub-filter has its own false-positive rate, and a query that is not in the set gets a chance to fool every one of them. If all sub-filters had the same rate p, the combined rate after s sub-filters would be

1 - (1 - p)^s   ≈   s * p

which grows without limit. If instead sub-filter i has rate p0 * r^i with r = 0.5, the combined rate is

1 - product of (1 - p_i)   <=   sum of p_i   <   p0 / (1 - r)   =   2 * p0

so the total stays under twice the first sub-filter's rate no matter how many are added. The price is that later sub-filters spend more bits per key to be stricter.

A worked example

Start with capacity 4 and target 0.05. Each new sub-filter doubles the capacity and halves the target. compound is the combined rate with that many sub-filters:

Five sub-filters hold 124 keys with a combined rate of 0.093885, under 2 * 0.05 = 0.1. Five sub-filters all at 0.05 would give 0.226219.

Costs

Lookups touch several sub-filters, and the stricter ones need more bits per key, so a scalable filter uses more memory than a well-sized plain one. It earns its place when n is genuinely unknown, such as a crawler's set of seen URLs. Systems that know their sizes, like per-file filters in an LSM database, size each filter exactly and avoid the machinery.

Common mistakes

• Checking only the newest sub-filter. Every key added before the last growth would become a false negative.
• Growing too early or too late. A new sub-filter is allocated by the ADD that finds the newest one full, not by the ADD that fills it.
• Forgetting that a repeated key still counts toward capacity: ADD does not look for duplicates.
• Halving the target by hand for each step and drifting. Start from the previous target and multiply by 0.5.
• Sizing a sub-filter with the wrong n: it is sized for its own capacity, not the total.

Your exercise

The starter provides the sizing helper and the commands that only report state (FILTERS, TOTAL, SHAPE). You write INIT, ADD with growth, CHECK across all sub-filters, and COMPOUND.