UUtah Data Mining | Fall 2026 | L12: Steaming & Sampling

Overview

Streaming algorithms process an ordered sequence of items while retaining only a small summary, making them useful for routers, high-traffic websites, and datasets too large to fit in memory. The lecture develops uniform reservoir sampling for one or K items—with and without replacement—and weighted sampling, including a one-item weighted reservoir update and priority sampling for weighted samples without replacement.

Key takeaways

A streaming algorithm updates a compact summary as each item arrives, targeting space polynomial in log m and log |U| instead of storing all m items.
One-item reservoir sampling selects each of the first i stream items with probability exactly 1/i by replacing the current sample with probability 1/i.
For K-item uniform sampling without replacement, accept item i with probability K/i and, when accepted, evict a uniformly random reservoir item; each seen item then has inclusion probability K/i.
Weighted one-item reservoir sampling replaces the current choice with item j at probability wⱼ divided by cumulative weight, enabling proportional-to-weight selection in one pass.
Uniform samples capture common, well-supported structure but can miss rare outliers; algorithms that must detect anomalies need a different summary strategy.
Priority sampling handles weighted selection without replacement by ranking items with random weight-dependent priorities and retaining the K smallest.

Chapters

0:00 Streaming Algorithms and Sampling: Lecture Roadmap

The new section introduces streaming algorithms as a way to handle very large data under memory constraints.
Sampling is the main topic, with variants distinguished by whether sampling is weighted and whether repeats are allowed.

1:34 Coursework and Midterm Preparation

The clustering homework is due the following Tuesday; TA hours are available early in the week.
The midterm is scheduled for the following Thursday, covers material before streaming, and emphasizes major concepts.
Students may bring a reference sheet; preparing it is intended to help identify key ideas and formulas from earlier lectures.

8:51 Streaming Data as an Ordered Sequence

The input is written as an ordered stream A₁, A₂, …, Aₘ, with each item drawn from a domain U.
The order of arrival may be adversarial: an algorithm cannot assume items arrive in a convenient order.
The stream model focuses on limited memory rather than storing the entire input as a vector.

13:19 Small Summaries and One-Pass Updates

A streaming algorithm maintains a compact summary S and updates it from Sᵢ₋₁ when item Aᵢ arrives.
The target space is polynomial in log m and log |U|, rather than proportional to the full stream size.
Cluster centers illustrate a lossy summary: they represent the data without preserving every original point.

21:57 Router Traffic as a Streaming-Algorithm Use Case

Internet routers process packets containing source and destination IP addresses but cannot store every packet that passes through.
A compact running summary can help monitor traffic patterns and identify possible distributed denial-of-service attacks.
The router example motivates extracting useful statistics while packets continue to arrive.

26:01 Web Analytics, Large Files, and Time-Ordered Data

Busy websites and apps generate many clicks, searches, and page interactions that can be summarized without retaining every event.
For a dataset on disk or in the cloud, a one-pass summary can avoid loading the full dataset into computer memory.
Sequential streaming can reduce costly data movement; time-series and online prediction are related settings, though not identical to the strict streaming model.

32:02 Warm-Up: Maintaining an Average in a Stream

To track the average of real-valued items A₁ through Aᵢ, maintain both the count Cᵢ = i and the running sum Sᵢ.
Update the sum with Sᵢ = Sᵢ₋₁ + Aᵢ, then recover the average as Sᵢ / Cᵢ.
Keeping the current average alone is insufficient for a straightforward update; the count and sum form a compact, updateable summary.

38:04 Why Random Samples Summarize Common Structure

A random sample is a general-purpose summary that tends to retain evidence of large, well-supported clusters.
Rare outliers may be missed, so uniform sampling is a poor choice when finding exceptional or abnormal points is the goal.
In simple one-dimensional cases, tracking the maximum directly may be more appropriate than relying on a random sample.

41:38 Sampling With Replacement Versus Without Replacement

With replacement, independent draws may select the same item multiple times, producing an IID sample.
Without replacement, every selected item is distinct, but the draws are not independent.
The difference is small when the sample is tiny relative to the population, but matters more for large samples or weighted selection.

47:16 Reservoir Sampling for One Uniform Item

Initialize the reservoir with A₁, then process each later item Aᵢ using a fresh uniform random value U.
Replace the reservoir with Aᵢ when U < 1/i, so the new item is selected with probability 1/i.
The algorithm stores one item and a count while producing a uniform sample from the items seen so far.

51:37 Why One-Item Reservoir Sampling Stays Uniform

At step i, the new item Aᵢ enters the reservoir with probability 1/i.
For any earlier item Aⱼ, induction gives probability 1/(i−1) of being retained before the update.
The earlier item survives with probability 1−1/i, making its updated probability (1/(i−1)) × ((i−1)/i) = 1/i.

58:39 K Uniform Samples With Replacement

Run K independent copies of the one-item reservoir algorithm, each using separate randomness.
The resulting K draws are IID; different copies may select the same stream item.
This direct parallel construction gives a with-replacement sample without changing the single-item algorithm.

1:01:04 K-Item Reservoir Sampling Without Replacement

Initialize the reservoir with the first K distinct items, then process each later item Aᵢ.
Select Aᵢ for the reservoir with probability K/i; if selected, evict one of the K current items uniformly at random.
After processing i items, each item has probability K/i of appearing in the reservoir, which is a uniform sample without replacement.

1:08:12 Weighted Sampling and Probability-Proportional Selection

For item Aⱼ with nonnegative weight wⱼ, weighted sampling selects it with probability wⱼ divided by the total weight seen so far.
The cumulative weight can be maintained as the stream arrives, much like maintaining a count or sum.
Weighted selection appears in k-means++—where squared distance guides selection—and in importance sampling to focus samples on consequential items.

1:13:34 Weighted Reservoir Sampling for One Draw

Initialize the reservoir to A₁ and the cumulative weight to w₁; update the total as each new weight arrives.
For item Aⱼ, replace the current reservoir with probability wⱼ divided by the updated cumulative weight.
Independent copies extend the method to K weighted draws with replacement.

1:16:36 Priority Sampling for Weighted Samples Without Replacement

Weighted sampling without replacement needs a different method because the replacement decision depends on the current selected set.
Assign each item a random priority based on its weight and a uniform random value; an exponential-race form uses −ln(Uⱼ)/wⱼ.
Maintain the K smallest priorities in a priority queue; this yields a weighted sample without replacement, with expected amortized O(1) maintenance time per item.

Summary, takeaways, and chapters were generated by AI from the video's transcript and may contain errors. The video belongs to its creator, UofU Data Science.