Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Exponential decay — where it appears

A weighting in which an arrival's contribution halves every half-life, so recent counts dominate and nothing is ever fully forgotten. It is what monitoring systems run instead of a sliding window, and it answers a weighted-total question rather than a count over any interval.

Named by 3 essays across 2 fields — each of them below, with the objects they name alongside it.

Also named here as half life — the same set of essays touches all of them, so they are one junction rather than several.

decayedwindowed060120secondscount attributed to key 0half-life 4 s · window 5.77 s · burstythe same key, two questions

The counter with no window in it

A counter that fades by half every H settles, on a steady stream, at exactly the count of a window of 1.44H. That correspondence holds in the mean, on a steady stream, and nowhere else — and it is the reason a decayed counter is not an estimate of a windowed count for any window.

streaming · Decay fades a lazy table computed382,976fades an eager table would compute3,830,256fade multiplications (log scale)11,968 evictions, each comparing all 32 counters at one instant32 counters · half-life 4 s · bursty10× fewer

The fading nobody computes

Twelve thousand arrivals into thirty-two decayed counters cost 382,976 fade multiplications. An implementation that aged every counter on every tick would have cost 3,830,256, and the ratio is exactly the mean gap between arrivals — not a coincidence, and the reason the family is deployable.

practice · Decay 00.2500.5000.7501010203040age of an arrival, secondsweight it carries nowexponential, half-life 4.0 sbackward polynomial, α = 2, scale 4.0 sforward, β = 2, landmark 20 s backforward, β = 2, landmark 160 s backdotted: half weightweights at the moment of reading

A decay measured from where it started

An exponentially decayed counter is one number because its weights fade by elapsed time alone. Forward decay keeps a polynomial weight in one number too, by measuring each arrival from a fixed landmark. Its memory is then a share of the time since that landmark: at β = 2 an arrival counts half at 29% of that time. Anchored at the start of a stream, it takes 5.3 seconds to register a fourfold rise twenty seconds in and 83 seconds when the rise comes at five minutes.

streaming · Decay

Named alongside it

The objects these essays reach for when they reach for this one.

Half lifeState bitsStreaming modelTimestampArrival processEstimatorAmortisedDesign parameterEvictionFloating pointForward decayGuarantee

All concepts