PadhaikoAll subjects

Online and Streaming Algorithms

Advanced Algorithms (ENCT 467)

Open in the Padhaiko app

7.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 .

Definition

Online vs. Offline Algorithms

Classical Online Problems

  1. 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 .
  2. 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.
  3. 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 .
  4. 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 .

Definition

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)

Example 1

1

  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.
  2. 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 .

Answer:
  1. Ski rental ratios for : (), (, worst case), and ().
  2. 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 :

Classic Paging Policies and Bounds

  1. 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.
  2. LRU (Least Recently Used) & FIFO (First-In First-Out): Both are -competitive deterministically ().
  3. LFU (Least Frequently Used) & LIFO: Not competitive (unbounded ratio : an adversary repeatedly builds huge frequency on a stale page or thrashes the newest slot).
  4. 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.
Competitive Ratios of Paging / Caching Algorithms (Cache Size k)
AlgorithmTypeCompetitive RatioNotes
Belady's MINOffline optimal (optimal)Evicts farthest-in-future page
LRU / FIFO / FWFDeterministic onlineOptimal deterministic ratio
LFU / LIFODeterministic onlineUnbounded ()Vulnerable to adversarial thrashing
Randomized MarkingRandomized onlineBeats deterministic lower bound
Example 2

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 ():

  1. A: miss
  2. B: miss
  3. C: miss
  4. D: miss (evict LRU A)
  5. A: miss (evict LRU B)
  6. B: miss (evict LRU C)
  7. D: hit (move D to MRU)
  8. C: miss (evict LRU A)
  9. A: miss (evict LRU B)
  10. B: miss (evict LRU D)

Total LRU page faults .

Trace Belady's OPT (): 1–3. A, B, C: misses .

  1. D: miss! Next occurrences: A at step 5, B at step 6, C at step 8 evict farthest C, cache .

5–7. A, B, D: hits!

  1. C: miss! Next occurrences: A at step 9, B at step 10, D never again evict D, cache .

9–10. A, B: hits! Total OPT page faults . Ratio .

Answer:

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.

Definition

Data Stream Model and Frequency Moments

Given a stream of elements from universe with item frequencies , the -th frequency moment is:

Core Streaming Algorithms

  1. 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 .
  2. 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.
  3. 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.

Definition

Count-Min Sketch (Cormode–Muthukrishnan)

A Count-Min Sketch (CMS) is a integer table initialized to , paired with pairwise-independent hash functions :

Because all , (never underestimates). Setting and guarantees that with probability at least :

Distinct-Element and Second-Moment Sketches

Example 3

3

  1. 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.
  2. 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:

Answer:
  1. The CMS requires width , depth , and bytes ( counters).
  2. The CMS estimate is .

Exercises

Practice Exercises — Online and Streaming Algorithms

Question 1

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.

Answer:

Strict competitiveness requires (asymptotic adds ). For Ski Rental, any deterministic algorithm has worst-case ratio at least , whereas randomized ski rental achieves .

Question 2

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: C misses and evicts A ({B, C}), A misses and evicts B ({C, A}), B misses and evicts C ({A, B}), repeating for all requests faults.
  • OPT: On C (miss), A is needed before B, so evict B ({A, C}); A is a hit; on B (miss), C is needed next, so evict A ({B, C}); C is a hit; on A (miss), B is needed next, so evict C ({A, B}); B is a hit faults.

Ratio .

Answer:

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 ().

Question 3

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 .

Answer:

Algorithm R replaces a random slot whenever , inductively preserving uniform inclusion probability . For and , item remains in the reservoir with probability .

Question 4

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):

  1. a: {a: 1}
  2. b: {a: 1, b: 1}
  3. a: {a: 2, b: 1}
  4. c: map full ( keys) and c absent decrement all: a becomes , b becomes (evict b), leaving {a: 1}.
  5. a: {a: 2}
  6. d: {a: 2, d: 1}
  7. a: {a: 3, d: 1}
  8. b: map full and b absent decrement all: a becomes , d becomes (evict d), leaving {a: 2}.
  9. 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).

Answer:

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.

Question 5

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):

Answer:

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.

← Approximation and Optimization AlgorithmsAlgorithmic Applications and Emerging Topics →