Streaming Models, Guarantees & Complexity

From Conveyor Belts to Frequency Vectors

Imagine a checkout conveyor: items pass once, and a clerk keeps a small tally rather than saving every receipt. A streaming algorithm has the same problem at machine speed. It sees a sequence of updates, keeps a limited state, and answers a specified question. Before choosing a compact tally, we must decide what counts as an update, whether corrections can arrive, and how wrong an answer may be.

Suppose the stream is $A, B, A, C, B, A$. The exact counts are A: 3, B: 2, C: 1. We can describe them as a frequency vector indexed by all possible items: for a universe $\{A,B,C,D\}$, it is $(3,2,1,0)$. The vector is a mathematical description of the stream, not a requirement to store four counters. When the universe has billions of possible keys, storing one counter per key may defeat the memory budget. A query might ask for A's count, the number of distinct items, or whether any item is unusually frequent; these are different contracts.

For the conveyor, an arrival adds one. In a payment ledger, a reversal might subtract one. For an incident dashboard, events can also expire from a recent time window. These differences determine which conclusions remain true. We will use basic vectors, sums, inequalities, and probability; no prior sketch design is needed. The motivating question is: what can a small state honestly promise about an enormous changing stream?

Cash Registers, Turnstiles and Windows

Fix a universe of $U$ keys. Update $t$ is a pair $(i_t, \Delta_t)$; its frequency vector after $t$ updates is $f^{(t)}$, with $f_i^{(t)}=\sum_{s\le t,\;i_s=i}\Delta_s$. A cash-register stream has $\Delta_t \ge 0$, commonly $+1$. A turnstile stream permits negative changes. A strict-turnstile stream permits them but requires every coordinate $f_i^{(t)} \ge 0$ at every prefix. An ordinary, or general, turnstile stream need not satisfy that prefix condition. Example: $(+A,3), (-A,2)$ is strict; $(-A,1), (+A,2)$ reaches $-1$ and is general turnstile, although its final count is $1$. Some systems accept only integer updates; specifying the allowed update size matters as well.

A one-pass algorithm reads each update once in arrival order. Its state has at most $S$ bits; each update takes some time $T_u$ and each query some time $T_q$. The stream length $m$ counts updates, while $N=\sum_i f_i$ counts active items only when that sum is meaningful and nonnegative. With deletions, $m$ and $N$ can differ sharply; $\lVert f\rVert_1=\sum_i\lvert f_i\rvert$ is another possible scale. For $W$-event windows, retain only the most recent $W$ updates. For a time window, event timestamps, late arrivals, and the chosen clock become part of the definition. The window's vector is the sum of currently included updates, not necessarily the lifetime vector.

For a query value $q$, additive error $\varepsilon B$ means $\lvert\hat q-q\rvert\le\varepsilon B$ for a declared baseline $B$, such as $N$ or $\lVert f\rVert_1$. Multiplicative error $\varepsilon q$ means $\lvert\hat q-q\rvert\le\varepsilon\lvert q\rvert$ when that expression makes sense. At $q=0$, a purely relative guarantee requires exact zero. A randomized guarantee such as $\Pr_R[\lvert\hat q-q\rvert\le\varepsilon B]\ge1-\delta$ fixes the stream and query first and takes probability over algorithm randomness $R$. It does not automatically promise success for all possible queries at once or against an adversary that adapts to revealed randomness. In a distributed stream, we must also specify partitions, communication budget, merge rules, and whether updates are duplicated.

flowchart TD
    U["Updates (key, change)"] --> C{"Negative changes?"}
    C -->|No| A["Cash register"]
    C -->|Yes| P{"Every prefix nonnegative?"}
    P -->|Yes| S["Strict turnstile"]
    P -->|No| G["General turnstile"]
    U --> W["Window rule selects active updates"]
    A --> F["Frequency vector"]
    S --> F
    G --> F
    W --> F
    F --> Q["Query and error scale"]
    Q --> R["Claim needs memory, time, failure bounds"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class U,F navy; class A,S,W teal; class G,C,P crimson; class Q,R purple;

Reading a Streaming Guarantee Without Fooling Yourself

Consider a nonnegative frequency vector with total mass $N=\sum_i f_i$. If an estimator promises $\lvert\hat f_i-f_i\rvert\le\varepsilon N$, then for $N=1,000$ and $\varepsilon =0.01$, its allowed error is 10. This is useful for a key with count 400 and weak for a key with count 3. Dividing by $N>0$ gives $\lvert\hat f_i/N-f_i/N\rvert\le\varepsilon$: the same bound is an additive guarantee on the key's share. It is not a 1% relative guarantee on every count. At $N=0$, that division is undefined; the contract needs a separate rule.

Suppose a fixed query fails with probability at most $\delta$. If a fixed collection of $k$ queries is asked using the same randomized state, let $E_j$ be failure of query $j$. The union bound gives $\Pr(\text{at least one failure})\le\sum_j\Pr(E_j)\le k\delta$; independence is unnecessary. To guarantee that all 100 predetermined queries succeed with probability at least 0.99 by this argument, make each query's failure bound at most $0.01/100=0.0001$. This is a sufficient parameter choice, not proof that the failures really add up or that this memory cost is necessary. An adaptively selected query requires a theorem that explicitly covers adaptive choice; the fixed-query derivation cannot be reused without justification.

Memory claims also need units. An exact count in ${0,\ldots,m}$ requires at least $\lceil\log_2(m+1)\rceil$ bits of representation for that count, while a full exact vector of $U$ such bounded counters can be stored using $U\lceil\log_2(m+1)\rceil$ bits. The latter is an upper bound, not a universal lower bound: constraints on the vector or the supported query might allow smaller state. A claim of $O(\varepsilon^{-2}\log(1/\delta))$ counters is incomplete until counter widths, hash seeds, the universe encoding, and per-update work are included.

flowchart TD
    P["Premise: fixed stream, fixed query"] --> E["Each failure event has probability ≤ δ"]
    E --> C{"How many queries?"}
    C -->|One| O["Success probability ≥ 1−δ"]
    C -->|k fixed queries| U["Union bound: any failure ≤ kδ"]
    C -->|Chosen from answers| X["Stop: adaptive theorem needed"]
    U --> T["Choose δ ≤ target failure / k"]
    classDef navy fill:#17365D,color:#fff,stroke:#17365D;
    classDef teal fill:#147D84,color:#fff,stroke:#147D84;
    classDef crimson fill:#C6284D,color:#fff,stroke:#C6284D;
    classDef purple fill:#6C3BAA,color:#fff,stroke:#6C3BAA;
    class P,E navy; class O,U,T teal; class X crimson; class C purple;

Telemetry, Payments and Incident Windows

Approachable telemetry. A school counts library visits by room: $(+A),(+B),(+A),(+C),(+B),(+A)$ is cash register, with $f=(3,2,1)$ and six visits. If a mistaken scan is later canceled, model it as a negative update; whether the stream remains strict turnstile depends on the count at the cancellation prefix. If instead the dashboard asks for visits in the most recent four events, the active suffix is $A,C,B,A$, yielding $(2,1,1)$. A lifetime tally cannot answer that window query without additional information.

Production payments. Imagine 50,000 authorization events per second, a 24-hour retention horizon, one pass at ingestion, and 256 MiB of worker memory. A charge and a reversal must be keyed by the same intended entity; retries and duplicate delivery need a deduplication policy before frequencies mean “transactions.” A strict-turnstile assumption is defensible only if reversals always follow recorded charges in the order the worker sees. Late reversals and cross-region reordering can invalidate it. An approximate count used to prioritize investigation may tolerate an explicit additive bound and failure probability; a settlement amount should be reconciled exactly against the ledger. The stream model guides the design but does not certify business correctness.

Adversarial incident windows. A security dashboard asks for the top IPs during the last 15 minutes. An attacker may generate keys and watch published estimates. A theorem for a fixed stream with private randomness need not cover those adaptively chosen updates. Time windows also need a policy for late events and clock skew. If the arrival rate is 10,000 events per second, a 15-minute window can contain roughly 9 million events; specify whether the 256 MiB bound includes timestamps, keys, and state. Changing the threat model or window boundary changes the claim even if the query wording stays the same.

Design the Contract Before the Sketch

A streaming design starts with a question about data, then an update model, then a guarantee and resource budget. Test the contract with small sequences that expose its assumptions before considering an algorithm. The exercises below move from definitions to a review of a realistic specification. A complete answer states not only what works, but which changed input would invalidate the claim.