Streaming and the Multipass Model

Lecture 15 · CS 574: Randomized Algorithms · Fall 2026

Sariel Har-Peled

University of Illinois, Urbana-Champaign

The model and the questions

Sequential access; small memory

\[ s_1,s_2,\ldots,s_n,\qquad \text{workspace}\ll n,\qquad \text{passes}\in\{1,2,\ldots\}. \] One pass: retain a summary. Multiple passes: rescan the same input.

Task	Target
Secretary	Select the maximum immediately
Reservoir	Uniform \(k\)-subset of stream positions
Approximate median	Rank error \(\leq \varepsilon n/2+O(1)\)
Exact median	Sample, bracket, rescan
Heavy hitters	Retain every \(x\) with \(f_n(x)\geq\varepsilon n\)

Source: streaming.tex, Chapter 27. The order follows the notes except that the streaming model is introduced first. Memory bounds count words. Sampling is over occurrences, even when values repeat. Corrections are documented in CORRECTIONS.txt; the original notes have not been changed.

Secretary: the threshold strategy

Random order; distinct ranks; known \(n\)

\[ (\alpha_1,\ldots,\alpha_n) \sim\text{uniform permutation of }n\text{ ranked candidates}. \] Reject \(1,\ldots,r-1\); retain \(M=\max_{j<r}\alpha_j\). \[ \tau=\min\{i\geq r:\alpha_i>M\}, \qquad \text{success}\iff \alpha_\tau=\max_{j\leq n}\alpha_j. \]

Condition on the maximum’s position \(I\)

\[ \Pr[I=i]=\frac1n,\qquad \Pr[\tau=i\mid I=i]=\frac{r-1}{i-1}\quad(i\geq r). \] \[ \boxed{P(r)=\frac{r-1}{n}\sum_{i=r}^{n}\frac1{i-1}} \qquad(2\leq r\leq n). \]

Independence alone, as stated in the source, does not imply uniform ranks. Use random order, or independent identically distributed continuous qualities. If no candidate exceeds the threshold, no hire is made; this is failure. For r=1, hire the first candidate, giving success probability 1/n.

Secretary: why \(1/e\)?

Harmonic sum

\[ \ln\frac{n}{r-1} =\int_{r-1}^{n}\frac{dx}{x} \leq\sum_{j=r-1}^{n-1}\frac1j \leq\int_{r-2}^{n-1}\frac{dx}{x} =\ln\frac{n-1}{r-2}\quad(r\geq3). \] \[ \frac{r-1}{n}\longrightarrow x\in(0,1) \quad\Longrightarrow\quad P(r)\longrightarrow x\ln(1/x). \]

Optimize the threshold

\[ g(x)=-x\ln x,\qquad g'(x)=-\ln x-1,\qquad g''(x)=-1/x<0. \] \[ \boxed{r=1+\lfloor n/e\rfloor,\qquad P(r)\longrightarrow 1/e.} \]

Reservoir sampling: two constructions

Random priorities

\[ U_i\overset{\mathrm{iid}}{\sim}\operatorname{Unif}(0,1), \qquad S_t=\text{positions with the }k\text{ smallest priorities}. \] Every \(k\)-subset has probability \(\binom tk^{-1}\); heap update: \(O(\log k)\).

Constant-time replacement

Store the first \(k\) positions. For \(t>k\): \[ \begin{aligned} J_t&\sim\operatorname{Unif}\{1,\ldots,t\};\\ J_t\leq k&:\quad S[J_t]\gets (s_t,t);\\ J_t>k&:\quad S\text{ unchanged}. \end{aligned} \] \[ \Pr[\text{insert }t]=k/t,\qquad \Pr[\text{evict slot }j\mid\text{insert}]=1/k. \]

Reservoir sampling: uniformity of the whole set

Induction: \(S_t\) is uniform among the \(k\)-subsets of \([t]\)

Base \(t=k\): \(S_k=[k]\). Fix \(K\subseteq[t]\), \(|K|=k\). \[ t\notin K:\quad \Pr[S_t=K] =\frac1{\binom{t-1}{k}}\left(1-\frac kt\right) =\frac1{\binom tk}. \] \[ \begin{aligned} t\in K:\quad \Pr[S_t=K] &=\sum_{j\in[t-1]\setminus K} \Pr[S_{t-1}=(K\setminus\{t\})\cup\{j\}] \frac kt\frac1k\\ &=\frac{t-k}{\binom{t-1}{k}}\frac kt\frac1k =\frac1{\binom tk}. \end{aligned} \]

\[ \boxed{\text{space }O(k),\quad \text{time/update }O(1),\quad n\text{ unknown}.} \] For \(t<k\), retain all \(t\) occurrences.

Sampling a median: ranks and guarantee

Conventions

Order keys \((\text{value},\text{original position})\) lexicographically. \[ R_B(j)=j\text{th smallest key},\qquad m=\lceil n/2\rceil. \] Draw \(k\) independent uniform samples with replacement; \(k\) odd. \[ Z=R_S((k+1)/2),\qquad a=\left\lfloor\frac{(1-\varepsilon)n}{2}\right\rfloor,\quad b=\left\lceil\frac{(1+\varepsilon)n}{2}\right\rceil. \]

Approximate-median lemma

\[ 0<\varepsilon<\tfrac12,\quad k\geq\left\lceil\frac{12}{\varepsilon^2}\ln\frac2\delta\right\rceil \quad\Longrightarrow\quad \boxed{\Pr[R_B(a)\leq Z\leq R_B(b)]\geq1-\delta.} \] Use \(R_B(0)=-\infty\) at a boundary.

Approximate median: the Chernoff calculation

Too many samples below the lower bracket

\[ X_i=\mathbf1[e_i\leq R_B(a)],\qquad Y=\sum_{i=1}^{k}X_i. \] Dominate \(Y\) by \(Y'\sim\operatorname{Bin}(k,(1-\varepsilon)/2)\): \[ \mu=\mathbb E Y'=\frac{(1-\varepsilon)k}{2}\geq\frac k4, \qquad \frac k2=\frac{\mu}{1-\varepsilon}\geq(1+\varepsilon)\mu. \] \[ \begin{aligned} \Pr[Z<R_B(a)] &\leq\Pr[Y\geq k/2] \leq\Pr[Y'\geq(1+\varepsilon)\mu]\\ &\leq e^{-\varepsilon^2\mu/3} \leq e^{-\varepsilon^2k/12}\leq\delta/2. \end{aligned} \]

Reverse the order: \[ \Pr[Z>R_B(b)]\leq\delta/2 \quad\Longrightarrow\quad \Pr[Z\notin[R_B(a),R_B(b)]]\leq\delta. \]

Stronger sampling: bracket the true median

Two sample quantiles

\[ k=\Theta\!\left(\varepsilon^{-2}\ln\frac2\delta\right),\qquad k_-=\left\lfloor\frac{(1-\varepsilon)k}{2}\right\rfloor,\quad k_+=\left\lceil\frac{(1+\varepsilon)k}{2}\right\rceil. \] \[ L=R_S(k_-),\qquad H=R_S(k_+). \]

Simultaneous event \(\mathcal G\); probability \(\geq1-\delta\)

\[ R_B\!\left(\left\lfloor(\tfrac12-\varepsilon)n\right\rfloor\right) \leq L\leq R_B(m)\leq H \leq R_B\!\left(\left\lceil(\tfrac12+\varepsilon)n\right\rceil\right). \] \[ T=\{x\in B:L\leq x\leq H\} \quad\Longrightarrow\quad \boxed{|T|\leq2\varepsilon n+O(1).} \] Four Chernoff tails; enlarge the absolute constant in \(k\).

For sufficiently large n,k, the indicated sample ranks are valid. Handle small inputs directly and use sentinels for population boundary ranks. The sample can be independent with replacement or a uniform subset without replacement, using the next slide. Integer rounding changes only absolute constants.

Why reservoir samples have the needed tails

\(k\) positions without replacement; \(M\) marked positions

\[ X=|S\cap\text{marked}|,\qquad p=M/n,\qquad (a)_j=a(a-1)\cdots(a-j+1). \] \[ \mathbb E\binom Xj =\binom kj\frac{(M)_j}{(n)_j} \leq\binom kjp^j. \] For \(\lambda\geq0\), set \(u=e^\lambda-1\geq0\): \[ \begin{aligned} \mathbb E e^{\lambda X} &=\mathbb E(1+u)^X =\sum_{j=0}^{k}u^j\mathbb E\binom Xj\\ &\leq\sum_{j=0}^{k}\binom kj(up)^j =(1-p+pe^\lambda)^k. \end{aligned} \]

Same upper-tail bound as \(\operatorname{Bin}(k,p)\). Count unmarked positions for the lower tail.

Exact median: sample, bracket, filter

Parameters and pivots

\[ \varepsilon=n^{-1/3},\qquad \delta=n^{-c},\qquad k=\min\{n,\lceil C_c n^{2/3}\ln n\rceil\}. \] Uniform reservoir \(S\); find \(L=R_S(k_-)\) and \(H=R_S(k_+)\).

One scan after choosing the pivots

\[ \alpha=|\{x\in B:x<L\}|,\qquad T=\{x\in B:L\leq x\leq H\},\qquad q=m-\alpha. \] \[ \boxed{1\leq q\leq|T|\quad\Longrightarrow\quad R_T(q)=R_B(m).} \] On \(\mathcal G\): \(|T|=O(n^{2/3})\) and \(1\leq q\leq|T|\).

If k=n, store the whole input and compute the median directly. Use the same original-position tie breaker in both passes. If alpha were instead the one-based rank of L, the correct output rank would be m-alpha+1.

Median selection: account for every comparison

Two comparisons per stream key

\[ C_{\mathrm{scan}}\leq2n,\qquad |S|=\Theta(n^{2/3}\log n),\qquad |T|=O(n^{2/3})\quad\text{on }\mathcal G. \]

Sorting versus selecting the sample pivots

\[ \begin{array}{c|c|c} \text{pivot computation}&\text{sample cost}&\text{total, including sorting }T\\ \hline \text{sort }S&O(k\log k)&2n+O(n^{2/3}\log^2 n)\\ \text{two linear-time selections}&O(k)&2n+O(n^{2/3}\log n) \end{array} \]

The sharper bound uses selection for \(L,H\); sorting the sample costs an extra \(\log n\).

From \(2n\) to \(\frac32n\) comparisons

Randomize which pivot is compared first

Let \(a=|T|\). Interior keys cost \(2\); exterior keys cost \(1+\operatorname{Ber}(1/2)\). \[ C_{\mathrm{scan}}\mid(L,H) \ \overset d=\ n+a+\operatorname{Bin}(n-a,\tfrac12). \] \[ \mathbb E[C_{\mathrm{scan}}\mid L,H]=\tfrac32n+\tfrac12a,\qquad C_{\mathrm{scan}}\leq\tfrac32n+\tfrac12a+O(\sqrt{n\log n}) \quad\text{w.h.p.} \]

Simpler: always compare to \(L\) first

\[ C_{\mathrm{scan}}=n+(n-\alpha)=2n-\alpha. \] On \(\mathcal G\), \(\alpha\geq n/2-\varepsilon n-O(1)\), so \[ \boxed{C_{\mathrm{scan}}\leq\tfrac32n+\varepsilon n+O(1) =\tfrac32n+O(n^{2/3}).} \]

Exact median in two passes

Pass 1 → pivots → pass 2

\[ \underbrace{\text{reservoir of }k=\Theta(n^{2/3}\log n)}_{\text{pass 1}} \ \longrightarrow\ (L,H)\ \longrightarrow\ \underbrace{(\alpha,T)}_{\text{pass 2}} \ \longrightarrow\ R_T(m-\alpha). \] Select sample pivots in \(O(k)\); sort \(T\).

Known \(n\); fixed \(c>0\)

\[ \boxed{ \begin{aligned} \text{space}&=O(n^{2/3}\log n),\\ \text{comparisons}&\leq\tfrac32n+O(n^{2/3}\log n),\\ \Pr[\text{success}]&\geq1-n^{-c}. \end{aligned}} \] Cap \(|T|\) at \(4\lceil n^{2/3}\rceil+4\); overflow or invalid \(q\) → failure.

Every reported answer is exact. Retrying requires additional passes.

Deterministic thinning: merge and halve

A level-\(h\) summary represents \(2^h s\) keys

\[ A,B:\ |A|=|B|=s,\qquad C=\operatorname{sort}(A\cup B),\qquad \operatorname{thin}(A,B)=(C_2,C_4,\ldots,C_{2s}). \] \[ (\text{level }h-1)+(\text{level }h-1)\longrightarrow\text{level }h. \]

Binary carries through the levels

Sort incoming blocks of \(s\) keys. Merge equal levels until unique. \[ \text{at most one stored summary per level} \quad\Longrightarrow\quad \boxed{\text{space }O(s\log(n/s)+s).} \] For the derivation, \(n=s2^h\); distinct, consistently tie-broken keys.

Thinning: the rank error accumulates

Count invariant

\(F_h(x)\): original keys \(\leq x\); \(C_h(x)\): summary keys \(\leq x\). \[ \boxed{0\leq F_h(x)-2^h C_h(x)\leq E_h,\qquad E_h=h2^{h-1}.} \]

Induction

Child summaries contain \(a,b\) keys \(\leq x\); parent contains \(\lfloor(a+b)/2\rfloor\). \[ \begin{aligned} F_h(x)-2^h C_h(x) &=e_1+e_2+ 2^{h-1}\left(a+b-2\left\lfloor\frac{a+b}{2}\right\rfloor\right),\\ 0&\leq e_1,e_2\leq E_{h-1},\\ E_h&=2E_{h-1}+2^{h-1}=h2^{h-1},\qquad E_0=0. \end{aligned} \] Thus \(Q_r\), the \(r\)th retained key, satisfies \[ \boxed{2^hr\leq\operatorname{rank}_B(Q_r)\leq2^hr+h2^{h-1}.} \]

Thinning: an exact-median bracket

Choose summary indices far enough apart

\[ w=2^h=n/s,\qquad E=hw/2,\qquad \ell=\left\lfloor\frac{m-E}{w}\right\rfloor,\quad u=\left\lceil\frac m w\right\rceil. \] \[ L=Q_\ell,\ H=Q_u \quad\Longrightarrow\quad \operatorname{rank}_B(L)\leq w\ell+E\leq m\leq wu\leq\operatorname{rank}_B(H). \] Use \(L=-\infty\) if \(\ell\leq0\).

Second pass: filter and select

\[ |T|=O(E+w)=O\!\left(\frac ns\log\frac ns\right). \] \[ s=\Theta(\sqrt n) \quad\Longrightarrow\quad \boxed{\text{two passes},\qquad\text{space }O(\sqrt n\log n).} \] Sort \(T\) in \(O(\sqrt n\log^2 n)\), or select in \(O(\sqrt n\log n)\) time.

For general n, choose a power-of-two block size s near sqrt(n), pad with distinct +infinity sentinels to N=s*2^h<2n, and keep the original target rank m. The padded keys are virtual and are not retained in the second-pass candidate buffer. If the upper bracket is a sentinel, the same bound applies to the real keys below it. This removes the divisibility assumption without changing the asymptotic space bound. The times displayed are final extraction times, not the running time of the entire first pass.

More passes, less storage

Munro–Paterson (1980)

Repeatedly narrow a pair of filters; finish when all candidates fit in memory. \[ \boxed{p\text{ passes}:\quad O\!\left(n^{1/p}(\log n)^{\,2-2/p}\right)\text{ storage}.} \] \[ p=2:\quad O(\sqrt n\log n). \]

Keep track of accumulated rank error

\[ \text{one thinning step: exact even ranks in the merged summaries;} \] \[ \text{repeated thinning: original-rank uncertainty grows with the level.} \]

(Munro & Paterson, 1980, Theorem 2).

The notes state O(n^(1/p) log n) for all p. The cited theorem instead gives the displayed logarithmic exponent. The two-pass specialization agrees. The paper thins child summaries before merging; the previous slides prove the notes’ merge-then-thin variant separately. Original paper: https://sites.cs.ucsb.edu/~suri/cs290/MunroPat.pdf

Heavy hitters: the target set

At prefix length \(t\)

\[ f_t(x)=\sum_{i=1}^{t}\mathbf1[s_i=x],\qquad \mathcal H_t=\{x:f_t(x)\geq\varepsilon t\},\qquad 0<\varepsilon<1. \] \[ |\mathcal H_t|\,\varepsilon t\leq\sum_x f_t(x)=t \quad\Longrightarrow\quad \boxed{|\mathcal H_t|\leq\lfloor1/\varepsilon\rfloor.} \]

Candidate summaries

\[ \text{random sample: }\mathcal H_t\subseteq\text{sampled values} \quad\text{with high probability}; \] \[ \text{counter algorithm: }\mathcal H_t\subseteq S_t \quad\text{deterministically}. \] Candidate sets may include values below the threshold.

Random sampling: missing a fixed hitter

Uniform reservoir of \(m\leq t\) positions

For fixed \(x\) with \(f=f_t(x)\geq\varepsilon t\): \[ \begin{aligned} \Pr[x\text{ absent}] &=\frac{\binom{t-f}{m}}{\binom tm} =\prod_{j=0}^{m-1}\frac{t-f-j}{t-j}\\ &\leq(1-f/t)^m \leq(1-\varepsilon)^m \leq e^{-\varepsilon m}. \end{aligned} \] The probability is \(0\) if \(m>t-f\).

\[ \boxed{m\geq\left\lceil\frac1\varepsilon\ln\frac1\delta\right\rceil \quad\Longrightarrow\quad \Pr[x\text{ absent}]\leq\delta.} \] If the stream has fewer than \(m\) positions, keep them all.

Random sampling: capture every hitter

Union bound at a fixed prefix

\[ \Pr[\exists x\in\mathcal H_t:x\text{ absent}] \leq|\mathcal H_t|e^{-\varepsilon m} \leq\frac1\varepsilon e^{-\varepsilon m}. \] \[ \boxed{m=\left\lceil\frac1\varepsilon\ln\frac1{\varepsilon\delta}\right\rceil \quad\Longrightarrow\quad \Pr[\mathcal H_t\subseteq\text{sampled values}]\geq1-\delta.} \]

Cost and scope

\[ \text{space }O\!\left(\varepsilon^{-1}\log\frac1{\varepsilon\delta}\right), \qquad \text{update }O(1). \] Fixed \(t\): the probability statement is over the reservoir randomness. An extra pass can count candidates exactly.

Deterministic counters: the update rule

\(k=\lceil1/\varepsilon\rceil\) counters; initially \(S=\varnothing\)

On arrival of \(x\), execute exactly one case: \[ \begin{array}{rll} 1.&x\in S:&c(x)\gets c(x)+1;\\[2pt] 2.&x\notin S,\ |S|<k:&S\gets S\cup\{x\},\quad c(x)\gets1;\\[2pt] 3.&x\notin S,\ |S|=k:&c(y)\gets c(y)-1\quad\text{for every }y\in S;\\ &&\text{delete zero counters; discard incoming }x. \end{array} \]

\[ \boxed{|S_t|\leq k,\qquad c_t(y)>0\ \ (y\in S_t),\qquad \text{space }O(1/\varepsilon).} \] Absent values have conceptual counter \(0\).

Deterministic counters: cancellation proof

Each full decrement cancels \(k+1\) distinct occurrences

Let \(D_t\) be the number of full-decrement events. \[ \sum_xc_t(x)=t-(k+1)D_t\geq0 \quad\Longrightarrow\quad D_t\leq\frac{t}{k+1}. \] A value loses at most one occurrence per cancellation: \[ \boxed{f_t(x)-D_t\leq c_t(x)\leq f_t(x).} \]

Every heavy hitter survives

\[ f_t(x)\geq\varepsilon t \quad\Longrightarrow\quad c_t(x)\geq\varepsilon t-\frac{t}{k+1}>0, \] \[ k=\lceil1/\varepsilon\rceil \quad\Longrightarrow\quad \frac1{k+1}<\varepsilon \quad\Longrightarrow\quad \boxed{\mathcal H_t\subseteq S_t\quad\text{for every }t\geq1.} \]

The bounds to retain

Problem	Bound
Secretary threshold	\(r\sim n/e\), success \(\to1/e\)
Uniform reservoir	\(O(k)\) words, \(O(1)\) update
Approximate median	\(k=O(\varepsilon^{-2}\log(1/\delta))\)
Randomized exact median	\(2\) passes; \(O(n^{2/3}\log n)\) words
Its comparison count	\(\frac32n+O(n^{2/3}\log n)\)
Deterministic exact median	\(2\) passes; \(O(\sqrt n\log n)\) words
Sample all heavy hitters	\(O(\varepsilon^{-1}\log(1/(\varepsilon\delta)))\) words
Deterministic candidates	\(\lceil1/\varepsilon\rceil\) counters

\[ \text{uniformity}\quad+\quad \text{concentration}\quad+\quad \text{rank brackets}\quad+\quad \text{cancellation}. \]

References

Chapter 27, Streaming and the Multipass Model, course notes.

Motwani, R., & Raghavan, P. (1995). Randomized algorithms. Cambridge University Press. https://doi.org/10.1017/cbo9780511814075

Munro, J. I., & Paterson, M. (1980). Selection and sorting with limited storage. TCS, 12, 315–323. https://doi.org/10.1016/0304-3975(80)90061-4