When old events must expire
A running total answers how many events have ever occurred, but it does not answer how many occurred in the last hour. If individual event times are discarded, a later subtraction is impossible. Keeping every bit in the window is exact and uses bits for a window of positions. We will trade exactness for a much smaller summary when a controlled relative error is acceptable.
Definition 17.1.1
(Active window and true count)
The input is a binary stream , with one bit per integer time. Fix integers and . After processing time , the active window is the set of positive integer times satisfying . Its true count is . A one at time has expired at time if .
The time index advances even when a zero arrives. All bounds below are deterministic: no random input, hashes or independence are assumed.
Buckets and the update rule
Definition 17.1.2
(Bucket summary)
A bucket represents a consecutive block in the ordered sequence of one events, not necessarily consecutive time positions. It stores its size, a power of two, and the timestamp of its newest one. A bucket summary is a list of buckets which, read from oldest to newest, partition all ones that have not been completely discarded, with sizes nonincreasing in this order.
A bucket may include expired ones, but only the oldest retained bucket can straddle the window boundary.
After the bit at time arrives, perform these steps in order:
- Discard every bucket whose newest timestamp is at most ; all of its ones have expired.
- If , append a new bucket of size 1 and timestamp . If , append nothing.
- While some size has more than buckets, choose the smallest such size and merge its two oldest buckets. The new bucket has twice their size and the newer of their two timestamps. Repeat until every size occurs at most times.
The two oldest equal-sized buckets are adjacent: because sizes are nonincreasing, all equal sizes occur in one contiguous block. Replacing those two by their union preserves both chronological order and nonincreasing sizes. The loop terminates because every merge reduces the number of buckets. Discarding precedes the merge so fully expired blocks do not occupy space; a boundary-straddling block must be kept because it still contains an active one.
For a query, add the sizes of all buckets except the oldest. If the oldest has size 1, add 1; otherwise add half its size. Call the resulting estimate . An empty summary returns zero. Every bucket newer than the oldest lies entirely in the window: its oldest one is later than the newest one in the retained oldest bucket, which itself is active.
Theorem 17.1.3
(Deterministic error and memory)
For every binary stream and every , the procedure returns an estimate satisfying
If , the estimate is exactly zero. At most buckets are stored. Each needs a size and timestamp; in a finite run to time , this is bits using absolute timestamps.
Proof
(Companion mass, then error and space)
Companion mass. A bucket of size is created by merging two size- buckets when that size has at least buckets. At creation there are at least other size- buckets newer than the merged pair. Their combined mass is at least . Later merges preserve that mass, and while the bucket remains the oldest retained bucket none of those newer ones can have expired: each is later than its active newest one. Thus the true window count includes at least newer ones, regardless of how they have since been grouped.
Error. If no bucket remains, every represented one has expired; all ones previously discarded were already expired when discarded, so . If the oldest bucket has size 1, its one is active and all newer buckets are active, giving an exact count. Otherwise let its size be and let of its ones be active. Since its newest one is active, . All newer buckets are counted exactly, so the absolute error is . The companion argument gives , so , proving the displayed relative bound.
Space. If the oldest bucket has size , those newer companions all lie in a window of positions, so and hence . The same bound applies to every newer bucket because sizes are nonincreasing. Sizes are powers of two from through at most ; there are at most possible sizes, each with at most buckets. This proves the bucket bound. Absolute timestamps through require bits each; the size also fits within that order for stored buckets. The theorem does not count the cost of storing the input externally or guarantee a worst-case constant update time.
Proof X-ray
The merge rule pays for the uncertainty of the oldest bucket
The only uncertainty in the estimate is how many of the oldest bucket's ones are active; every newer bucket is counted exactly. The proof therefore needs one inequality, a lower bound on the true count in terms of the oldest size , and the merge rule is what supplies it. Two features of the rule are used. Merging only when a size exceeds copies guarantees that equal-sized buckets remain at the moment of creation. Merging the two oldest of them guarantees that those survivors are newer, so they stay active as long as the merged bucket itself is retained. Expiry enters through the newest timestamp: a retained bucket has an active newest one, which gives and keeps the companions inside the window. The space bound reuses the same inequality against the window length, , so error and memory are controlled by a single counting fact.
The first example traces the update rule on a short run, including one expiry.
Worked example 17.1.4
(Expiry and the half-bucket estimate)
Let , , and take six consecutive ones. After times 1, 2, 3 the singleton buckets at 1 and 2 merge, leaving , where each pair is (size, newest timestamp). At time 4 the state is . At time 5, merging the oldest singleton pair gives . At time 6, the first bucket has newest timestamp 2, which is at the cutoff , so it is discarded. The final state is and the estimate is , whereas the exact count over times 3 through 6 is 4. The error is 1, below the general relative bound . Although this example happens to have no expired one in its oldest remaining bucket, its timestamp alone does not say so.
Worked example 17.1.5
(A merge cascade and its companion)
Let , , and take seven consecutive ones. As above, after time 5 the state is , and time 6 appends . At time 7 the cutoff is , so nothing expires. Appending gives three singletons, so merge into . Now size 2 has three buckets, , so the two oldest merge into . The final state is . The bucket was created with newer companion of size , namely , whose mass is . The estimate is against the true count ; the error is at most , and also at most .
Worked example 17.1.6
(Edge case: every one expires)
Let , , and process . After time 2 the state is . At time 3 the cutoff is , so is discarded, leaving ; the estimate equals . At time 4 the cutoff is , so is discarded too. The summary is empty and returns zero, which equals , as the theorem requires. The two zeros created no bucket, yet each advanced the cutoff.
Counterexample mode
The newest timestamp does not reveal the boundary split
With and , compare the histories and at time 6. Both summaries are : the size-2 bucket joins times 3 and 4 in the first stream, and times 2 and 4 in the second. Their window counts are 3 and 2 respectively, so the summary cannot give an exact answer for both. Simply counting every retained bucket in full overestimates the second history.
Common mistake
(Running the expiry step only when a one arrives)
Zeros create no bucket, but they still advance time, and expiry depends on time. An implementation that discards buckets only when keeps both buckets of the edge-case example above after time 4 and reports instead of . The discard step must run at every time index.
Design implications
Increasing improves the proven relative bound and increases storage. For a requested , choosing yields error at most ; this is a sufficient choice, not a proof of optimality. The method estimates a count of ones, not a sum of arbitrary signed or weighted values. It uses arrival order as event time; delayed events or deletion of an arbitrary past one require a different contract. Duplicate arrivals count twice, and independently generated summaries cannot simply be added if their represented events overlap.
The bound is deliberately conservative: even a bucket completely inside the window is halved if it is oldest and has size greater than one. Storing the oldest timestamp too would identify some fully active buckets, but would not reveal how many interior timestamps cross a boundary in general.
Common mistake
(Reading the half-bucket estimate as a claim about the split)
A half-bucket estimate is a guaranteed choice based on the stored information, not an assertion that half the events actually expired. In the first example the oldest bucket was entirely active, yet it was counted as instead of . The guarantee concerns the worst case over histories with the same summary.
Practice with solutions
Quick check
(For , , process . List the buckets after time 4 and the estimate.)
Check the cutoff before appending.
Solution · Answer
After time 3, the state is . At time 4 the cutoff is 1, so no bucket expires; append . The state is , and the estimate is . The true count is 3.
Quick check
(For , , process . Find the state and count at time 6.)
Zeros still move the cutoff.
Solution · Answer
At time 5 the cutoff is 2, so is discarded. The remaining singleton buckets are . At time 6, the cutoff is 3, so is discarded. The state is ; both estimate and true count are 1. Zeros advance the cutoff even though they create no buckets.
Quick check
(To guarantee relative error at most , give a valid and bucket bound for .)
Use and the bucket count in the theorem.
Solution · Answer
Take , because . Since , the theorem gives at most buckets. This is an upper bound, not an assertion that all are simultaneously achievable.
Quick check
(Why does retaining a bucket whose newest timestamp equals violate the stated update contract? What can go wrong if its full size is counted?)
Compare with the strict inequality in the definition of the window.
Solution · Answer
The active times satisfy the strict inequality , so every event in that bucket has expired. Counting it in full includes old events. For instance, a lone one at time 1 with must no longer be counted at time 2.
Quick check
(An implementation merges the two newest equal-size buckets instead of the two oldest. Which step of the proof fails?)
Look at where the companions sit relative to the merged bucket.
Solution · Answer
At creation it need not leave equal-sized buckets newer than the merged bucket. Those older companions can expire while the new bucket remains active, so the lower bound on active newer mass no longer follows. A different proof would be needed; this observation alone does not establish the alternative algorithm's exact error.