When Old Data Must Stop Counting
Imagine a shop manager asking, “How many customers entered recently?” A lifetime counter answers how many have ever entered, which becomes less useful every day. A landmark window restarts at a chosen boundary such as midnight. A sliding window continually forgets observations as they become too old. Exponential decay forgets gradually: an observation never falls off a cliff, but its influence shrinks with age.
Suppose one request arrives in each minute with values $[2,5,1,7,3,4]$. After the sixth arrival, a count-based window of the last three observations contains $[7,3,4]$ and sums to $14$. A five-minute event-time window at clock time 12:06 might contain a different set if requests arrived irregularly or late. With half-life two minutes, the weight of a four-minute-old event is $2^{-4/2}=1/4$ rather than zero.
These models answer different questions. “Last 1,000 transactions” gives every transaction equal relevance regardless of traffic speed. “Last 15 minutes” follows elapsed event time. “Since deployment” uses a landmark. “Recent behavior matters progressively more” suggests decay. Before choosing a data structure, specify which clock defines age, whether the boundary is inclusive, what happens to late events, and whether approximation error is allowed.
A window is a rule for assigning present relevance to past events: hard windows use weight zero or one, while decay uses intermediate weights. “Recent” is not a data-structure setting until the population, clock, boundary, and late-data policy are explicit.
| Concept | Intuitive meaning | Exact example | Non-example or boundary | Assumption | Question answered |
|---|---|---|---|---|---|
| Landmark window | Remember everything since a fixed reset point | Events since midnight UTC | A boundary that moves after every event | The landmark has agreed semantics | What happened since a named start? |
| Count window | Keep the most recent $W$ arrivals | Last 1,000 payments | Last ten minutes when traffic varies | Arrival order defines recency | What happened in the last $W$ items? |
| Time window | Keep events whose timestamps lie in a recent interval | Event times in $(t-15\text{ min},t]$ | Last 1,000 events | A clock and boundary convention are defined | What happened during recent elapsed time? |
| Damped window | Give older events smaller weights | Weight $2^{-a/H}$ at age $a$ and half-life $H$ | Abruptly deleting an event at age $H$ | The decay law expresses relevance | What is the age-weighted total now? |
| Exponential histogram | Compress a recent binary count into timestamped power-of-two buckets | At most a small number of buckets of each size | Exact storage of every bit | Insertion-ordered binary stream under the stated variant | How many ones occurred in the recent window? |
| Watermark | Claim about event-time completeness | No more events before 12:00 expected after watermark 12:00 | The server’s current processing time | A bounded-lateness or source-progress contract | When may event-time state be finalized? |
When Old Data Must Stop Counting
Six events arrive in order with values $2,5,1,7,3,4$ at event times 1, 2, 4, 7, 8, and 10 minutes.
- At the sixth arrival, the last-three-events window contains $7,3,4$ and sums to $14$.
- At event time 10, define a right-closed five-minute window $(5,10]$. It contains events at times 7, 8, and 10, again summing to $14$—but this agreement is accidental.
- At event time 8, the last-three-events window contains values $1,7,3$ and sums to $11$; the window $(3,8]$ also contains those three events. Add ten events at time 7.5 and the two models immediately diverge.
- With half-life two minutes, the event at time 4 has weight $2^{-(10-4)/2}=1/8$ at time 10. Its weighted contribution is $1/8$.
Reflection: which model should a fraud rule use when an attacker can generate thousands of requests in one second: the last 1,000 attempts or the last five minutes? State the behavior each model emphasizes rather than choosing by habit.
Count Windows, Time Windows and Decay
Let the stream contain observations $(x_i,\tau_i)$, where $\tau_i$ is event time. A count window of width $W$ at arrival index $n$ contains indices $i$ satisfying $n-W+1\le i\le n$. A time window of duration $T$ evaluated at time $t$ contains events satisfying $t-T\lt\tau_i\le t$ under a right-closed convention. Changing either inequality changes boundary membership and must be tested.
A landmark window beginning at $L$ contains events with $L\lt\tau_i\le t$. A damped window assigns a nonincreasing age weight $g(t-\tau_i)$. Exponential decay with rate $\lambda\gt0$ uses $g(a)=e^{-\lambda a}$. If the half-life is $H$, then $\lambda=\ln 2/H$ and $g(a)=2^{-a/H}$. Its weighted sum is
$$ S(t)=\sum_{i:\tau_i\le t}x_i e^{-\lambda(t-\tau_i)}. $$
For in-order events, advancing from $t$ to $t+\Delta$ multiplies the old state by $e^{-\lambda\Delta}$ before adding new contributions. This recurrence is algebraically exact for the exponential kernel; it is not a general property of arbitrary decay functions.
An exponential histogram for a binary stream groups ones into buckets whose sizes are powers of two and whose timestamps locate their newest or oldest relevant endpoints, depending on the convention. Limiting the number of equal-sized buckets forces merges. A query sums complete buckets and estimates the partially overlapping oldest bucket, making that boundary bucket the source of error. Standard space is logarithmic in the window length and inversely related to the requested relative error, with exact constants depending on the maintained bucket limit and query rule.
A smooth histogram is a reduction for functions with a suitable smoothness property. It maintains multiple suffix summaries beginning at selected times and deletes intermediate starts whose values have become sufficiently close. If removing a prefix changes the function only moderately whenever two nested suffix values are close, one retained suffix can approximate the desired window boundary. This does not make every streaming statistic windowable: the smoothness premise is essential.
Out-of-order event time adds another axis. Processing-time order says when the system saw an event; event time says when it occurred. A watermark or allowed-lateness policy determines when old state can be finalized. Dropping late data, retracting earlier answers, and delaying output are different semantic choices, not mere implementation details.
flowchart TD
A[Define relevance of age] --> B{Hard or gradual?}
B -->|Hard| C{Boundary moves?}
B -->|Gradual| D[Choose decay kernel]
C -->|No| E[Landmark window]
C -->|By arrivals| F[Count window]
C -->|By clock| G[Time window]
D --> H[Exponential decay]
G --> I{Events in timestamp order?}
I -->|Yes| J[Expiration structure]
I -->|No| K[Watermark and lateness policy]
F --> L[Exponential histogram for binary counts]
G --> M[Smooth-histogram reduction when function is smooth]
E --> N[Lifetime-style summary since landmark]
H --> O[Multiplicative state update]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,C,I navy;
class E,F,G teal;
class D,H,O purple;
class J,L,M,N teal;
class K crimson;
| Model or theorem | Exact scope | Required assumptions | What it does not say | Counterexample or consequence |
|---|---|---|---|---|
| Count window | Last $W$ arrivals by a declared order | A total arrival order and $W\ge1$ | That the window spans a fixed duration | At burst rate, 1,000 events may cover milliseconds |
| Event-time window | Events satisfying a timestamp predicate such as $t-T\lt\tau_i\le t$ | Timestamp source, query time, boundary, and lateness semantics | That all qualifying events have arrived | A delayed event belongs historically but is absent at first query |
| Exponential recurrence | Prior weighted sum scales by $e^{-\lambda\Delta}$ | Exponential kernel, consistent units, and no numerical underflow that changes policy | A hard cutoff after one half-life | At age $H$, weight is $1/2$, not zero |
| Exponential histogram guarantee | Approximate recent-one count from compressed buckets | Binary or suitably transformed nonnegative updates, ordered expiration, specified bucket invariant | Exact answers or arbitrary signed sums | Negative updates can invalidate monotone bucket accounting |
| Smooth histogram reduction | Approximates a window statistic using selected suffix instances | Nonnegative function with the theorem’s monotonicity and smoothness conditions | Every mergeable sketch is smooth-window compatible | A statistic can change sharply when a tiny prefix expires |
| Watermark | System-specific assertion of progress in event time | Source or engine contract about future lateness | Proof that no earlier event can ever arrive unless the contract is absolute | Network recovery can deliver data behind the watermark |
The boundary is where hard-window uncertainty lives: complete buckets can be counted exactly or by their own sketch guarantees, while only the oldest overlapping bucket is partly inside. Compression is safe only when the maintained invariant bounds that bucket’s possible contribution relative to the target quantity.
Expiration Error and Smoothness Arguments
Consider counting ones in the last $W$ positions. Store timestamped buckets with power-of-two sizes and allow at most $k$ buckets of each size. When a new singleton makes too many size-one buckets, merge the two oldest into one size-two bucket; repeat upward if necessary. Bucket sizes preserve the number of represented ones exactly, but a query boundary may cut through the oldest retained bucket.
Let the oldest overlapping bucket have size $B$. If the query counts half of that bucket, its absolute error is at most $B/2$. The bucket invariant ensures enough more-recent mass exists relative to $B$, allowing this boundary error to become a controlled fraction of the estimated recent count. The precise relative-error constant depends on whether the implementation keeps $k$, $k+1$, or another number of buckets per size and on how it estimates the oldest bucket; one must cite and test the chosen variant rather than repeat a floating slogan.
Smooth histograms use a different idea. For suffixes $A\supseteq B$, suppose $f(B)$ is close to $f(A)$. A smoothness condition says that appending the same continuation $C$ keeps $f(B\cup C)$ close to $f(A\cup C)$. The algorithm retains starts only where the suffix value drops materially. At query time, the true window start lies between two retained starts, so monotonicity and smoothness sandwich the window value. If a function is nonmonotone or can jump after a small prefix change, this argument breaks.
Out-of-order input can break simple expiration proofs because timestamps no longer increase with arrival order. A bucket’s “oldest” event may be inserted late, and already emitted answers may change. Event-time systems therefore buffer until a watermark, allow bounded corrections, or declare late events dropped. Each option changes completeness, latency, or stability.
flowchart TD
A[Ordered nonnegative stream] --> B[Create newest singleton bucket]
B --> C{Too many buckets of one size?}
C -->|Yes| D[Merge two oldest equal sizes]
D --> C
C -->|No| E[Maintain geometric bucket invariant]
E --> F[Place query cutoff]
F --> G[Sum fully included buckets]
F --> H[Estimate oldest overlapping bucket]
H --> I[Absolute boundary error at most half its size]
E --> J[Newer mass lower-bounds scale]
I --> K[Relative-error guarantee for chosen variant]
J --> K
A -. signed updates break monotonic mass .-> X[Proof fails]
F -. late timestamp changes past boundary .-> Y[Need watermark or correction]
classDef navy fill:#17365D,color:#fff,stroke:#17365D;
classDef teal fill:#147D84,color:#fff,stroke:#0D565B;
classDef crimson fill:#C6284D,color:#fff,stroke:#861B35;
classDef purple fill:#6C3BAA,color:#fff,stroke:#472675;
class A,B,C navy;
class D,E,G teal;
class F,H,I,J purple;
class K teal;
class X,Y crimson;
Expiration Error and Smoothness Arguments
An exponential histogram represents recent ones with bucket sizes, ordered oldest to newest, $[8,4,4,2,2,1,1]$. A query boundary cuts through the size-eight bucket, while every later bucket lies fully inside.
- The fully included mass is $4+4+2+2+1+1=14$.
- The true contribution of the size-eight boundary bucket could range from $0$ to $8$ without more internal timestamps, so the true count lies from $14$ to $22$.
- Estimating half the boundary bucket reports $18$. The absolute error is at most $4=B/2$.
- This example alone does not prove a relative error of $4/18$. The maintained rule limiting equal-sized buckets is what relates $B$ to the newer mass; write that invariant before claiming a general ratio.
- If exact stored timestamps reveal that six of the eight represented ones lie after the cutoff, the true count is $20$ and the half-bucket estimate errs by $2$.
Assumption-breaking variation: allow updates $+1$ and $-1$. A size-eight bucket may have near-zero net contribution even though its stored “mass” is eight. The nonnegative monotonic argument relating bucket size to recent total no longer applies; identify a turnstile-window method with a separate proof instead of reusing this guarantee.
| Proof tool or viewpoint | What it establishes | Assumptions | Tightness or limitation | Failure case |
|---|---|---|---|---|
| Boundary-bucket argument | Only one partially overlapping bucket causes expiration uncertainty | Timestamp-ordered buckets with correct endpoint metadata | Absolute error depends on boundary-bucket size | Out-of-order insertion places an old event in a “new” bucket |
| Geometric bucket invariant | Boundary bucket is small relative to sufficiently recent mass | Nonnegative binary count and bounded buckets per size | Constants depend on the exact variant | Signed deletions destroy the mass comparison |
| Smoothness sandwich | A retained suffix approximates a nearby window start | Monotonicity plus the required smoothness implication | Applies only to functions satisfying that definition | Statistic flips from zero to one when one old event expires |
| Exponential semigroup | Decayed state can be advanced by multiplication | Kernel $e^{-\lambda a}$ with consistent time units | Does not represent an abrupt legal or policy horizon | Treating one half-life as if everything older vanished |
| Watermark reasoning | Bounds how long event-time state remains open | Enforced source-progress or bounded-lateness contract | A heuristic watermark permits late corrections or loss | Offline client uploads events hours late |
| Exact replay comparison | Measures actual error on sampled windows | Complete retained ground truth and representative sampling | Empirical evidence is not a universal theorem | Evaluation omits burst and late-data periods |
Fraud Bursts, Telemetry and Changing Popularity
In fraud detection, a card used ten times within five minutes may be suspicious even if ten uses across a year are normal. A time window represents the rule directly, while a count window changes duration with platform traffic. Yet event time may come from an untrusted device; processing time may be harder to forge but mixes network delay with user behavior.
For telemetry, recent error counts and latency quantiles drive alerts. Distributed services generate out-of-order events, duplicate retries, and uneven shard traffic. Windowed quantiles require a window-capable summary or pane composition with an explicit approximation analysis; subtracting two ordinary quantile sketches is generally invalid. A watermark trades answer latency against completeness.
For recommendations or trends, exponential decay gives graceful turnover rather than a sharp midnight reset. A half-life expresses a comprehensible policy: after $H$ time units, evidence counts half as much. But decay can preserve coordinated manipulation for a long tail, and changing the half-life changes the product meaning, not merely memory use.
An adversary can exploit boundaries by scheduling activity just outside a hard window and resuming immediately afterward. Several overlapping windows or a decayed score can reduce cliff effects, though neither replaces identity, deduplication, or adversarial rate controls. Clock skew and timestamp forgery can also move events across a boundary unless timestamps are trusted or normalized.
Fraud Bursts, Telemetry and Changing Popularity: Sliding Windows & Time Decay
A community forum records posts at minutes $1,2,4,8,9,10$ with toxicity flags $[0,1,1,0,1,1]$. At minute 10, moderators want the number of flagged posts in the last five minutes using $(5,10]$.
- The included event times are 8, 9, and 10, with flags $0,1,1$; the exact answer is $2$.
- A last-five-events count window includes times 2, 4, 8, 9, and 10 and reports $4$. It answers a different question.
- With half-life five minutes, compute decayed flag weight at minute 10: events at 2, 4, 9, and 10 contribute $2^{-8/5}+2^{-6/5}+2^{-1/5}+1\approx2.65$.
- Model selection: use the hard time window for a policy literally defined as “within five minutes”; use decay for a ranking signal where smooth aging is intended.
Success criteria: reproduce all memberships and weights to two decimals, state the boundary convention, and show that an event arriving late with event time 4 is excluded from the current hard window even though it arrived now. Explain whether it should alter a previously emitted minute-6 result.
Fraud Bursts, Telemetry and Changing Popularity: Sliding Windows & Time Decay
A payment platform ingests $250{,}000$ authorization events per second across 300 partitions. It needs per-account five-minute attempt counts, refreshed within two seconds, with no more than $2\%$ relative counting error above a threshold of 50. Mobile clients may be offline for two minutes; timestamps can be skewed or malicious.
Theory-to-practice choice: use server receipt time for the immediate blocking rule because it is trusted and monotone enough for operational expiration. Maintain an exact deque for low-volume accounts and a bounded approximate structure only where cardinality and memory justify it. Compute event-time analytics separately with a two-minute watermark allowance and correction records; do not let untrusted client time move an authorization outside the safety window.
Evidence: bucket-size and per-key state distributions; exact-vs-approximate replay around counts 45–55; late-event delay histograms; duplicate rates; clock-skew distributions; p99 update/query latency; memory under coordinated account sprays; false-block and missed-burst labels; and behavior at boundary instants.
Risks: a relative-error guarantee near zero is weak, hot accounts can dominate state, late arrivals can revise analytics, and attackers can pace attempts immediately outside one hard boundary. Add deduplication, overlapping shorter and longer horizons, state caps with explicit fallback, and audit logging.
Decision: deploy only if the conservative lower count bound still exceeds the block threshold for automatic action, sampled exact replay demonstrates the required error rate, and the overload fallback preserves a documented safety behavior. Otherwise keep approximation for prioritization and require exact verification before blocking.
Choose the Right Memory of the Past
Choosing a memory model is a semantic design decision. Start with the question the system must answer, express it as a membership or age-weight function, and only then select a summary. A correct lifetime sketch wrapped in an ambiguous window policy still produces the wrong metric.
Practice: Choose the Right Memory of the Past
Use events $(value,event\ time)$: $(3,1),(5,2),(2,5),(8,6),(4,10),(7,11)$, observed at processing time 12. Unless stated otherwise, use the right-closed interval $(t-T,t]$.
Tier 1 — Definitions. Define landmark, count, time, and exponentially decayed windows. At $t=12$, list the members of the last-three-events window and the five-time-unit window. Expected: values $8,4,7$ versus $4,7$. State why neither is a subset relation in general.
Tier 2 — Decay. With half-life $H=5$, compute each weight $2^{-(12-\tau_i)/5}$ and the weighted sum. Provide a table of age, weight, and contribution. Checkpoint: the newest event has the greatest weight, and advancing all events by the same elapsed time multiplies the total by one common factor.
Tier 3 — Expiration proof. For bucket sizes $[8,4,4,2,2,1,1]$ cut through the first bucket, derive the interval $[14,22]$ and midpoint estimate $18$. Name the invariant still needed to turn absolute error four into a general relative guarantee.
Tier 4 — Counterexamples. Give one case where a count window covers less than a second, one where it covers a day, one late event that changes a previously complete event-time window, and one signed-update stream that invalidates nonnegative bucket reasoning.
Tier 5 — Interpretation. Match each requirement to a model: legal records since filing date; last 500 quality inspections; requests in the last ten minutes; popularity with a seven-day half-life. Include clock, boundary, and late-data semantics.
Tier 6 — Professional design. Write a one-page window contract for a telemetry alert. Include population, key, event identity, event and processing clocks, width or half-life, inclusivity, approximation $(\varepsilon,\delta)$ where relevant, watermark, allowed lateness, correction policy, deduplication, merge behavior, state cap, overload fallback, and exact-replay audit.
Debugging prompts: if results jump at midnight, check for an accidental landmark reset; if historical results keep changing, inspect watermark and correction policy; if counts become negative, verify whether the proof assumed nonnegative updates; if two shards disagree, verify time units and boundary inclusivity.
Stretch goal: compare a single five-minute hard window with exponential decay of half-life five minutes and with two overlapping windows of one and fifteen minutes. Explain which detects sharp bursts, which turns over smoothly, and which retains multi-scale evidence.
Rubric (10 points): definitions and memberships 2; decay derivation 2; expiration reasoning 2; valid counterexamples 2; operational contract 2. Full credit requires distinguishing event time from processing time and stating a late-data consequence.
Decision checklist: define the population, clock, boundary, horizon or half-life, ordering, allowed lateness, correction policy, and error budget; then test expiration, skew, duplication, bursts, and adversarial timing. A sliding window is not automatically event-time correct, a half-life is not a cutoff, and a mergeable lifetime sketch is not automatically subtractable. The next step is to combine these temporal contracts with linear sketches, sparse recovery, and distributed merge rules without losing their assumptions.
Next in the Series
In Linear Sketches, l0-Sampling & Sparse Recovery, we'll explore Treat sketches as linear measurements of dynamic vectors..