Growing and Ageing a Filter Without Rebuilding It

A filter or sketch is sized once, from an estimate of how many keys it will hold. When the estimate is wrong, the structure degrades rather than fails: a Bloom filter that receives twice its design load does not overflow, it simply returns false positives at a rate that has climbed from a fraction of a percent to double digits. A hash table in the same position would grow, rehash, and keep its guarantee. The absence of a resize path is a real limitation, and the two standard responses — add more filter rather than widen the existing one, and let old evidence decay rather than delete it — each solve the problem by changing what the structure stores rather than how much of it there is.

Why in-place growth is impossible

Rehashing a hash table works because the table stores the keys. A Bloom filter stores only bits, and a bit records that some key hashed to a position; it does not record which. To move the contents into a larger array, the filter would need to recompute every key’s $k$ positions under the new $m$, and the keys are not available. The same argument applies to a Count-Min sketch, whose cells hold the summed counts of unknown keys, and to a HyperLogLog, whose registers hold maxima with no record of the producing key.

Any growth scheme must therefore preserve the old state as-is and add capacity alongside it. The structures differ in how gracefully they can do that, and the difference is the subject of this article.

A scalable Bloom filter keeps a list of ordinary filters, each with its own bit array, its own $k$, and its own hash function. Insertion goes to the newest filter; if that filter is at its capacity, a new one is allocated at a larger size and insertion continues there. A lookup tests every filter in the list and returns positive if any of them is.

The naive version has a problem: the overall false-positive rate is

$$ 1 - \prod_{i=0}^{\ell-1} \left(1 - \varepsilon_i\right) \approx \sum_{i=0}^{\ell-1} \varepsilon_i $$

so a filter with $\ell$ layers each at 1% has an overall rate approaching $\ell$ percent. The fix is to make each successive layer stricter by a geometric factor: layer $i$ is built for error $\varepsilon_0 r^i$ with $r < 1$. Then the sum converges:

$$ \sum_{i=0}^{\infty} \varepsilon_0 r^i = \frac{\varepsilon_0}{1 - r} $$

Choosing $r = 0.5$ and $\varepsilon_0 = \varepsilon/2$ gives a total error below $\varepsilon$ regardless of how many layers are added. The cost is that later layers are denser — halving the target error costs a fixed number of extra bits per key, so with $r = 0.5$ each layer is allotted about 1.44 more bits per key than the previous one — and the total space becomes a geometric series rather than a sum. That series converges, so the whole structure stays within a constant factor of a single filter sized for the final key count and the tightest error, at the price of the denser layers being allocated in full even if the set never grows into them.

The same construction gives growth in the other direction. A filter can start small and add layers as needed, which is what makes it usable when the key count is unknown at construction. The lookup cost grows with the number of layers, since every layer is probed: a filter that has grown to eight layers costs eight times the probes of a single-layer filter. That cost is the reason the layered design is used for slowly growing sets and not for high-throughput ones, and why a periodic rebuild into a single filter is worthwhile once growth stops.

Deletion by forgetting

The alternative to growing is ageing: instead of removing keys, reduce the weight of old observations so that they stop influencing the estimate. For a bit array there is no weight to reduce — a bit is set or clear — so ageing requires a structure with counters, such as a counting filter, and the counter’s decay becomes the mechanism.

A decaying counter increments on each observation and is multiplied by a factor $\lambda < 1$ at fixed intervals, or equivalently reduced by an amount proportional to its current value. The effective window is governed by $\lambda$: after $t$ intervals a contribution has weight $\lambda^t$, so with $\lambda = 0.99$ and one interval per minute, a contribution retains half its weight after about 69 minutes, since $\ln 0.5 / \ln 0.99 \approx 69$. That half-life is the single parameter that controls the trade between responsiveness and stability.

Applying decay to every counter on every interval is a full pass over the structure, which defeats the purpose for a large sketch. The standard trick is lazy decay: store with each counter the timestamp of its last update, and compute the decayed value at read time as $\text{value} \cdot \lambda^{,\text{now} - t}$. No background pass is needed, and a counter that is never touched costs nothing. The price is that every read performs a power or exponential, and that counters which are never read accumulate stale values in memory without being corrected.

Forward decay removes the arithmetic dependence on wall-clock time. Instead of decaying stored values, each observation is weighted by a function of its arrival time and a fixed reference point: $w(t) = \lambda^{t - L}$ with $L$ a fixed landmark in the past. The weight is computed once at insertion, and the decayed aggregate is a sum of weights that never needs to be recomputed. Sliding a window then means summing the contributions whose timestamps fall inside it, and the same weights serve every window because they are anchored to the landmark rather than to the query time. The method requires that the weights not underflow: with a landmark far in the past, $\lambda^{t-L}$ for a recent $t$ can exceed the range of a double, which is why the landmark must be advanced periodically and the stored aggregates rescaled.

Windowed cardinality without deletion

HyperLogLog cannot decrement, so a sliding window is built from buckets: one sketch per time interval, with the window estimate obtained by merging the buckets that overlap it. With one-minute buckets and a one-hour window, that is sixty sketches merged per query, each at the register count needed for the target accuracy. The space is sixty times a single sketch, which is the direct cost of windowing a maximum-based structure.

Two details make the difference between a usable and an unusable windowed sketch. First, bucket boundaries quantise the window: an estimate for the last 37 minutes either rounds to 37 buckets or interpolates between 36 and 37, and the quantisation error is largest when the window is short. Second, the merge cost per query grows with the window length in buckets, so a query rate of thousands per second over a sixty-bucket window is sixty thousand register-wise maximum operations per second — small for a few thousand registers, not small for a million.

The alternative is to age the registers themselves. A register holding a rank has no timestamp and no count, so it cannot be decayed; the maximum is all that survives. This is the structural reason cardinality sketches window badly while frequency sketches window well, and it is worth knowing before choosing a structure for a workload that needs a moving window.

What the two strategies cost

Strategy	Space overhead	Per-query cost	Deletion
Layered filter, r = 0.5	geometric, bounded by a constant factor	One probe per layer	No
Rebuild on threshold	1× between rebuilds	One probe	No, but state is fresh
Decaying counters	1× plus timestamps	One exponent per read	By weight only
Bucketed window	Window length × single sketch	Merge across buckets	Yes, at bucket granularity

The comparison that matters is against rebuilding. A filter rebuilt from the live set every time the error climbs has exactly the right contents and one layer, but the rebuild requires the live set to be available and requires a full pass over it. When the live set is itself the thing being approximated — a cache whose contents are the keys, a stream whose distinct values are the question — the rebuild is possible; when the keys have already been discarded, only layering or ageing is.

Choosing the half-life

The decay parameter is the only knob, and it is usually set by the question rather than by the data. A sketch meant to answer “what is hot right now” wants a half-life comparable to the cache’s own eviction horizon: a contribution that has aged past several half-lives is negligible, and a half-life much longer than the horizon means the sketch lags reality, while one much shorter means the estimate is dominated by noise from a handful of recent events. A half-life much shorter than the query interval produces estimates that fluctuate with the sampling phase rather than with the underlying rate.

The second consideration is counter resolution. Decay reduces every value, and a counter that decays below one unit cannot be distinguished from zero. With integer counters and a multiplier applied every interval, small counts vanish quickly: a count of 3 at $\lambda = 0.9$ is 1 after about ten intervals and gone shortly after. Floating-point counters avoid the cliff at the cost of space and determinism, and fixed-point counters with a fractional part are the usual compromise. A decayed counter that rounds to zero silently discards evidence that the structure was built to retain, which is the failure mode to check for when a decaying sketch reports fewer events than the traffic plainly contains.