Skip to content
Tutorials Center
My learning

Topics

Lesson 198 of 225 ยท Advanced Topics

Online and Streaming Algorithms

Learn online and streaming algorithms in Python: one-pass Boyer-Moore majority vote, count-min sketch, running and sliding statistics and reservoir sampling.

Every algorithm so far assumed the whole input was sitting in memory, ready to be read as often as you like. Real data often does not behave that way. A web server sees billions of requests a day; a sensor never stops sending numbers; a network router sees packets once as they fly past. You cannot store everything, and you cannot go back.

Online algorithms must produce answers as the input arrives, without knowing what comes next. Streaming algorithms go a step further: they read the data in one pass (or a few) using memory far smaller than the input, often O(1) or O(log n). In this lesson you will learn the Boyer-Moore majority vote, a count-min sketch for approximate counting, running and sliding statistics, and a recap of reservoir sampling. You will also see what it costs to decide without knowing the future.

Offline versus online versus streaming

Model What you know Memory Example
Offline The whole input in advance As much as you like Sort a list, then answer queries
Online Only the items so far; decisions are final Usually unlimited Cache replacement, ski rental
Streaming Items arrive once, in order Sublinear, tiny Counting distinct IPs on a router

Streaming algorithms usually trade exactness for memory: they answer a question approximately, or with a small chance of error, in far less space.

Boyer-Moore majority vote

Problem. Given a long stream of votes, find the item that appears more than half the time (the majority element), if one exists.

Brute force. Count every item with a dictionary: O(n) time but O(k) memory for k distinct values. Sorting also works in O(n log n).

Streaming idea. Keep one candidate and one counter. Imagine pairing off each vote for the candidate against a vote for something else: they cancel. A true majority has more than half the votes, so it cannot be cancelled out completely.

  • If the counter is 0, adopt the current item as the candidate.
  • If the item equals the candidate, increment the counter; otherwise decrement it.
TEXT
stream:     A  B  A  C  A  A  B  A
candidate:  A  A  A  A  A  A  A  A
count:      1  0  1  0  1  2  1  2   (at count 0 the next item is adopted)

Careful: when the count hits 0, the next item becomes the new candidate. Here the count drops to 0 twice, but each time the next item happens to be A again, so A is the final candidate.

The algorithm uses O(1) memory and one pass. If a majority is not guaranteed, the surviving candidate may be meaningless, so a second pass (or a count) is needed to verify.

Python Boyer-Moore majority vote with verification

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

For the stream ABACAABA, A appears 5 times out of 8, more than half. For ABCABC no item does, and the candidate it returns is just the last survivor, which is why the verification pass exists. The proof is short: a majority element has more occurrences than all other items combined, so even if every other item cancels one of its votes, at least one vote survives.

Elements that appear more than n/3 times

The same cancelling idea extends to larger thresholds. An element that appears more than n/k times can be found with k - 1 candidates: at most k - 1 values can exceed that share. For n/3 there are at most two such values, so keep two candidates with two counters.

  1. For each value: if it equals a candidate, increase that counter; else if a counter is 0, take the value as a new candidate; else decrease both counters (three different values cancel each other out).
  2. The survivors are only candidates. Count them in a second pass and keep those with more than n // 3 occurrences.
Python Boyer-Moore for n/3

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Time is O(n) and space O(1). Skipping the verification pass is the classic mistake: the counters never prove a candidate is frequent enough.

Counting frequencies in small space: count-min sketch

Problem. Estimate how often each item appeared in a huge stream (for example, page visits per URL) without a dictionary entry for every distinct item.

A count-min sketch is a small table of counters with d rows and w columns, plus d hash functions (one per row). To add an item, hash it with each row's hash and increment one counter per row. To estimate its count, read its d counters and take the minimum.

TEXT
          col0 col1 col2 col3 col4
row 0:  [  0    3    0    1    0  ]   hash0("cat") = 1
row 1:  [  2    0    0    3    1  ]   hash1("cat") = 3
row 2:  [  0    1    4    0    0  ]   hash2("cat") = 2
estimate("cat") = min(3, 3, 4) = 3

Collisions make a counter too high (other items land in the same cell), never too low. Taking the minimum across rows picks the least contaminated counter. So the estimate is always at least the true count and usually close. With width w and depth d, the overcount is at most about e/w times the total stream length, with probability about 1 - e^-d. Memory is d * w counters, independent of the number of distinct items.

Do not use Python's built-in hash() for strings in a sketch whose results you want to reproduce. It is randomized per process. The example below uses hashlib, which is stable.

Python A count-min sketch from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The sketch uses 256 counters to summarize 980 events over 303 distinct words. Heavy hitters like the come out almost exact; rare items can be overestimated, never underestimated. For real workloads the table is sized so that this error is tiny compared to the number of events.

Running statistics in O(1) memory

You do not need to store a stream to know its mean or its spread. Welford's algorithm updates the mean and the sum of squared deviations with each new value:

  • count += 1
  • delta = x - mean
  • mean += delta / count
  • m2 += delta * (x - mean) (using the new mean)

The variance is m2 / count (population) or m2 / (count - 1) (sample). This is more numerically stable than keeping sum(x) and sum(x*x), which can lose precision through catastrophic cancellation.

Python Welford running mean and variance

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Sliding window statistics

Often only the most recent k items matter: the last minute of requests, the last 7 days of temperatures. A window can be updated in O(1) per item, even though it holds k items.

  • Sliding sum or average: add the new item and subtract the one that leaves.
  • Sliding maximum: a monotonic deque keeps candidate indexes whose values decrease from front to back; the front is always the maximum. Each index enters and leaves once, so the total is O(n) for n items.

Unlike the other algorithms here, a sliding window must remember k items, so it uses O(k) memory, but k is chosen by you and independent of the stream length. See sliding window for the techniques in depth.

Python Sliding sum and sliding maximum over a stream

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Reservoir sampling recap

You met this in randomized algorithms: keep a uniform random sample of k items from a stream of unknown length using O(k) memory. The i-th item (counting from 1) enters the reservoir with probability k/i, replacing a random current member. It is the standard way to "look at a few representative lines" of a giant log, and it combines nicely with the other tools here: sample first, then compute statistics on the sample.

Online decisions: ski rental

An online algorithm cannot see the future, so its quality is measured by how it compares to an offline algorithm that knows everything: the competitive ratio. In the classic ski rental problem, renting skis costs 1 per day and buying costs B. You do not know how many days you will ski. The strategy "rent until you have paid B, then buy" never pays more than twice what a clairvoyant would have paid. No deterministic strategy can do meaningfully better.

Python Ski rental: rent until it equals the buying price

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Common mistakes

  • Skipping the verification pass. Boyer-Moore returns a candidate; it is only the majority if it is verified (or if the problem guarantees one exists).
  • Using the built-in hash() for sketches. String hashes change between runs. Use a stable hash such as hashlib.
  • Reading counts as exact. A count-min estimate can be too high. It is never too low, and the error is bounded, but it is not zero.
  • Naive variance formulas. sum(x*x) - n*mean*mean loses precision on large numbers. Use Welford.
  • Storing the stream "just in case". That defeats the purpose; decide up front exactly which small summary you need.

When to use these tools

Use streaming algorithms when the data is too large to store, arrives continuously, or can only be read once, and an approximate answer is acceptable: top-k trending items, unique visitors, monitoring dashboards, network analysis. If the data fits in memory and you need exact answers, the offline algorithms from earlier lessons are simpler.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How much memory does the Boyer-Moore majority vote candidate pass use?

    It keeps just a candidate and a counter. A second pass with one more counter verifies the result, still using O(1) memory.
  2. 2. Boyer-Moore returns 'C' for a stream with no majority. What does that mean?

    The candidate is only guaranteed correct when a majority exists. Otherwise it is whichever item survived the cancellations.
  3. 3. Why does a count-min sketch take the minimum of its counters?

    Other items can share a cell and raise it, but nothing lowers it. The minimum over independent rows is the closest estimate and is never below the true count.
  4. 4. What is the advantage of Welford's algorithm over keeping sum(x) and sum(x*x)?

    Welford updates the mean and squared deviations incrementally, avoiding the cancellation errors of subtracting two huge sums.
  5. 5. How much total work does the monotonic deque take to compute the sliding maximum over n items?

    Each index is appended once and removed at most once, so the amortized cost per item is constant.

Summary

  • Online algorithms decide as data arrives; streaming algorithms also read it once with tiny memory. Their quality is measured against what an offline algorithm could do.
  • Boyer-Moore majority vote finds the only possible majority element in one pass and O(1) memory; verify with a second pass when a majority is not guaranteed.
  • A count-min sketch estimates frequencies in fixed memory: it never underestimates, and the minimum across rows limits the overcount.
  • Welford's algorithm keeps a running mean and variance; a sliding window keeps sums in O(1) per item and maxima with a monotonic deque.
  • Reservoir sampling keeps a fair sample of a stream; ski rental shows the competitive ratio idea (at most 2 for rent-until-buy).

Next: Parallel and External Algorithms