Online and Streaming Algorithms
Open in the Padhaiko app7.1 Online algorithms
An online algorithm receives its input sequence piece by piece and must make an irrevocable decision at each step based solely on the prefix , without knowledge of future requests .
Online vs. Offline Algorithms
- Offline (Clairvoyant) Algorithm: Sees the entire input sequence in advance before producing any output or resource allocation.
- Online Algorithm: Processes each request immediately upon arrival; past choices cannot be undone even if future inputs reveal a better alternative.
Classical Online Problems
- The Ski Rental Problem: Renting skis costs unit per day, while buying skis costs units forever. The unknown number of ski days ends unexpectedly.
- Break-Even Strategy: Rent for days, then buy on day .
- List Update (Move-to-Front, MTF): Maintain an unsorted linked list of items under a sequence of
ACCESS(x)requests, where accessing position costs . Moving the accessed item to the front of the list keeps frequently accessed items near the head and achieves a -competitive ratio against any offline list-reordering algorithm. - Online Load Balancing (Graham's List Scheduling): Assign jobs arriving one by one with processing times onto identical parallel machines to minimize makespan (maximum machine load). Always assigning each incoming job to the currently least-loaded machine guarantees makespan at most .
- The Secretary Problem: ranked candidates arrive in random order and must be accepted or rejected immediately on interview. Rejecting the first candidates as a calibration sample and then hiring the first subsequent candidate better than all prior ones succeeds in picking the single best candidate with optimal probability .
7.2 Competitive analysis
Because online algorithms lack future knowledge, comparing their worst-case cost against an arbitrary constant fails to distinguish good strategies from bad ones. Competitive analysis (Sleator & Tarjan, 1985) benchmarks an online algorithm ALG against an all-knowing optimal offline algorithm OPT on the exact same worst-case input sequence .
c-Competitive Online Algorithm
For a minimization problem, a deterministic online algorithm is -competitive (strictly) if for every finite request sequence :
It is -competitive (asymptotically) if there exists a constant independent of the input length such that for all :
For a randomized online algorithm against an oblivious adversary (which fixes in advance without seeing the algorithm's random coin flips), is replaced by .
Deterministic vs. Randomized Competitiveness (Ski Rental)
- Deterministic Lower Bound: If a deterministic strategy buys on day , an adversary ends the trip on day : , while , giving ratio . If it buys on day , the adversary continues past days so and . Choosing minimizes the worst-case ratio at:
- Randomized Improvement: Selecting the buy day randomly according to a truncated exponential distribution reduces the expected competitive ratio against an oblivious adversary to:
1
- In the Ski Rental problem with daily rental cost and purchase price , compute the competitive ratio of the deterministic break-even algorithm (rent days, buy on day ) when the trip lasts (a) days, (b) days, and (c) days.
- In Graham's online list scheduling on machines, jobs arrive in order with durations . Trace the greedy assignment, compute the resulting makespan, and compare it with .
Ski Rental ratios for :
- (a) days (): Algorithm rents all days (), and offline also rents (). Ratio .
- (b) days (, worst case): Algorithm rents days then buys on day (), while buys on day (). Ratio .
- (c) days (): Algorithm pays , while . Ratio .
Graham's List Scheduling on machines for : Assign each job to the least-loaded machine (tie-breaking by lowest machine index ):
4(loads:[4, 0, 0])4(loads:[4, 4, 0])4(loads:[4, 4, 4])3(loads:[7, 4, 4])3(loads:[7, 7, 4])6(loads:[7, 7, 10])6(loads:[13, 7, 10])
Greedy makespan is . Since total work is , (indeed, assigning [6, 4] to , [6, 4] to , [4, 3, 3] to achieves ). Ratio .
- Ski rental ratios for : (), (, worst case), and ().
- Graham's list scheduling yields makespan vs. , giving competitive ratio .
7.3 Caching problems
In the paging (caching) problem, a fast cache holds at most pages while slow memory holds pages. Upon a page request :
- Cache Hit: is already in the cache (cost ).
- Cache Miss (Page Fault): is absent; it is loaded into cache (cost ), evicting one existing page if the cache already holds pages.
Classic Paging Policies and Bounds
- Belady's Offline Optimal (
MIN/ Farthest-in-Future): On a miss, evict the cached page whose next future request is farthest away (or never occurs again). Minimizes total page faults offline. - LRU (Least Recently Used) & FIFO (First-In First-Out): Both are -competitive deterministically ().
- LFU (Least Frequently Used) & LIFO: Not competitive (unbounded ratio : an adversary repeatedly builds huge frequency on a stale page or thrashes the newest slot).
- Marking Algorithms & Randomized Paging:
- Theorem (Sleator–Tarjan): No deterministic online paging algorithm can achieve a competitive ratio strictly better than .
- Randomized Marking Algorithm: Breaks the deterministic barrier by evicting a uniformly random unmarked page within each -distinct-page phase, achieving -competitiveness against an oblivious adversary.
| Algorithm | Type | Competitive Ratio | Notes |
|---|---|---|---|
Belady's MIN | Offline optimal | (optimal) | Evicts farthest-in-future page |
| LRU / FIFO / FWF | Deterministic online | Optimal deterministic ratio | |
| LFU / LIFO | Deterministic online | Unbounded () | Vulnerable to adversarial thrashing |
| Randomized Marking | Randomized online | Beats deterministic lower bound |
2
With an initially empty cache of size , process the request sequence:
using both (a) LRU and (b) Belady's offline optimal (OPT). Count the page faults for each and verify the competitive ratio .
Trace LRU ():
A: missB: missC: missD: miss (evict LRUA)A: miss (evict LRUB)B: miss (evict LRUC)D: hit (moveDto MRU)C: miss (evict LRUA)A: miss (evict LRUB)B: miss (evict LRUD)
Total LRU page faults .
Trace Belady's OPT (): 1–3. A, B, C: misses .
D: miss! Next occurrences:Aat step 5,Bat step 6,Cat step 8 evict farthestC, cache .
5–7. A, B, D: hits!
C: miss! Next occurrences:Aat step 9,Bat step 10,Dnever again evictD, cache .
9–10. A, B: hits! Total OPT page faults . Ratio .
LRU incurs page faults, while Belady's OPT incurs page faults, yielding ratio .
7.4 Streaming algorithms
A streaming algorithm processes a huge, continuous sequence of items in a single pass (or very few passes) using sublinear memory—typically bits, where is the universe size—and fast or update time per item.
Data Stream Model and Frequency Moments
Given a stream of elements from universe with item frequencies , the -th frequency moment is:
- : Number of distinct elements in the stream.
- : Total stream length.
- : Repeat rate / Gini homogeneity (self-join size).
Core Streaming Algorithms
- Reservoir Sampling (Vitter's Algorithm R): Maintains a uniformly random sample of size from a stream of unknown length in space:
- Store the first items in .
- For each arriving item , draw a uniform random integer ; if , replace .
- Proof by induction: At step , each prior item stays in with probability , matching the new item's inclusion probability .
- Misra–Gries Heavy Hitters (-Majority): Finds all items occurring strictly more than times using at most
(key, count)counters in space (generalizing Boyer–Moore's -counter majority algorithm for ). On each item: increment if tracked; else if counters used, insert with count ; else decrement all counters by and remove zeros. A second pass (if allowed) filters false positives. - Morris's Approximate Counter: Estimates a count up to using only bits by maintaining exponent and incrementing with probability (estimator has ).
7.5 Sketching techniques
A sketch is a compact, randomized summary data structure of a frequency vector that supports fast streaming updates and linearity (), allowing sketches from distributed servers to be merged directly.
Count-Min Sketch (Cormode–Muthukrishnan)
A Count-Min Sketch (CMS) is a integer table initialized to , paired with pairwise-independent hash functions :
UPDATE(i, c): For each row , set .QUERY(i)(Point Query): Return .
Because all , (never underestimates). Setting and guarantees that with probability at least :
Distinct-Element and Second-Moment Sketches
- Flajolet–Martin & HyperLogLog ( Distinct Count): Hashes each item uniformly to a binary string and tracks the maximum number of leading zeros across stochastic-averaging buckets (registers). Using harmonic mean across registers, HyperLogLog estimates within relative standard error using only to count billions of distinct elements.
- AMS / Tug-of-War Sketch ( Second Moment): Uses -wise independent Rademacher sign hashes to maintain . Since , averaging independent copies and taking the median estimates in space.
3
- Size a Count-Min Sketch to guarantee error at most with failure probability at most . Compute its table dimensions and total memory in bytes assuming -byte (-bit) counters.
- Suppose a Count-Min Sketch has rows after updates: Row 1 and Row 2 . If item hashes to and (1-indexed), what is the CMS frequency estimate ?
Compute Count-Min Sketch dimensions for , :
Total counters counters. At bytes each, memory bytes ().
Evaluate point query : Read Row 1 column 3: . Read Row 2 column 2: . Take the minimum across rows:
- The CMS requires width , depth , and bytes ( counters).
- The CMS estimate is .
Exercises
Practice Exercises — Online and Streaming Algorithms
Define -competitive ratio (strict and asymptotic) in competitive analysis. Explain why no deterministic algorithm for the Ski Rental problem (daily rent , purchase price ) can achieve a competitive ratio strictly less than , and state the randomized competitive ratio against an oblivious adversary.
Definition: An online minimization algorithm ALG is strictly -competitive if for all finite inputs , and asymptotically -competitive if for a constant independent of .
Deterministic lower bound for Ski Rental: Suppose a deterministic strategy buys on day :
- If , an oblivious adversary sets trip length . Then and , giving ratio (minimized at ).
- If (or never buys), setting gives and , so ratio .
Randomizing the buy day via an exponential distribution achieves against an oblivious adversary.
Strict competitiveness requires (asymptotic adds ). For Ski Rental, any deterministic algorithm has worst-case ratio at least , whereas randomized ski rental achieves .
Prove the Sleator–Tarjan lower bound showing that every deterministic online paging algorithm on a cache of size has competitive ratio at least (for pages). Illustrate this with a cyclic request sequence for and pages starting with in cache where LRU suffers faults over requests while OPT suffers only .
Lower bound proof ( pages): An adversary chooses the next request to be the unique page not currently in ALG's cache of size . Because ALG is deterministic, the adversary knows ALG's cache contents after every step and forces ALG to miss on every single request (). Meanwhile, Belady's OPT evicts the page requested farthest in the future; since there are only pages total, at least distinct requests must occur before the evicted page can reappear, so OPT misses at most once every requests (). Thus .
Illustration (, , initial cache , ):
LRU:Cmisses and evictsA({B, C}),Amisses and evictsB({C, A}),Bmisses and evictsC({A, B}), repeating for all requests faults.OPT: OnC(miss),Ais needed beforeB, so evictB({A, C});Ais a hit; onB(miss),Cis needed next, so evictA({B, C});Cis a hit; onA(miss),Bis needed next, so evictC({A, B});Bis a hit faults.
Ratio .
By always requesting the single page absent from a deterministic algorithm's size- cache over pages, an adversary forces a fault every step while OPT faults at most once per steps, proving ratio . Starting from cache () on , LRU faults times vs. OPT's times ().
State Reservoir Sampling (Algorithm R) for maintaining a uniform sample of size from a stream of unknown length , and prove by induction that after items, every seen item is in the reservoir with probability . Compute the exact probability that the nd item remains in a reservoir of size after items have arrived.
Algorithm R and inductive proof: Put the first items into . For each , draw uniformly; if , set .
- Base case (): Every item is in with probability .
- Inductive step: Assume at step each item () is in with probability . At step , enters with probability . An existing item is evicted only if hits its exact slot (prob. ), so it survives with probability . By independence:
Numerical probability (): After , item survives with probability . After , it survives with probability .
Algorithm R replaces a random slot whenever , inductively preserving uniform inclusion probability . For and , item remains in the reservoir with probability .
Trace the Misra–Gries heavy-hitters algorithm with ( counters) to find candidates occurring more than times in the -element stream:
Show the counter map after every element and state why a second pass is needed in general.
Trace Misra–Gries (, max counters):
a:{a: 1}b:{a: 1, b: 1}a:{a: 2, b: 1}c: map full ( keys) andcabsent decrement all:abecomes ,bbecomes (evictb), leaving{a: 1}.a:{a: 2}d:{a: 2, d: 1}a:{a: 3, d: 1}b: map full andbabsent decrement all:abecomes ,dbecomes (evictd), leaving{a: 2}.a:{a: 3}.
Output interpretation and second pass: The only surviving candidate is a (actual count ). A second pass is required in general because Misra–Gries guarantees no false negatives (every true heavy hitter with survives), but non-heavy hitters that arrive near the end of the stream can still remain in the counter table (false positives).
Misra–Gries finishes with {a: 3}, correctly identifying candidate a (true count ). A second pass verifies exact frequencies to eliminate false positives near the end of the stream.
Compare the Count-Min Sketch and HyperLogLog on purpose, update mechanism, and error guarantees. If a HyperLogLog sketch uses registers ( bits per register), compute its total memory in bytes and its relative standard error ().
Compare Count-Min Sketch vs. HyperLogLog:
- Count-Min Sketch estimates point frequencies in a integer table by incrementing hashed counters per item and taking the minimum across rows ( with prob. ).
- HyperLogLog estimates distinct-element cardinality () by partitioning items into buckets and recording the maximum leading-zero count in each bucket, combining buckets via a harmonic mean.
Memory and relative standard error for (-bit registers):
Count-Min Sketch tracks item frequencies with additive error, while HyperLogLog counts distinct elements using leading-zero registers. With -bit registers, HyperLogLog uses bytes and achieves standard error.