UUtah Data Mining | Fall 2026 | L13 : Streaming Freq Apx

Overview

Jeff Phillips develops streaming frequency approximation from the goal of estimating every item's count using small memory, then compares uniform sampling, the deterministic Misra–Gries algorithm, and the randomized Count-Min Sketch. He derives additive error guarantees in terms of stream length, contrasts Count-Min with Count Sketch's F2-based error, and closes with Apriori's frequency-based pruning for finding co-occurring items.

Key takeaways

Misra–Gries uses K labels and counters to guarantee a one-sided additive frequency error of at most m/K; choosing K = 1/ε gives error at most εm with deterministic updates.
Uniform sampling needs roughly ε⁻² log(1/δ) samples for additive error εm, making it substantially more memory-intensive than Misra–Gries when ε is small.
Count-Min Sketch uses K = 2/ε counters per row and t = log(1/δ) hash rows; taking the minimum row estimate guarantees an overcount of at most εm with probability at least 1 − δ.
Misra–Gries underestimates and Count-Min Sketch overestimates, while Count Sketch uses signed hashing and a median to obtain unbiased estimates with error related to F₂.
Apriori reduces combinatorial search by discarding infrequent single items before counting pairs; in the lecture's receipt example, items 6 and 9 form the pair meeting the four-occurrence threshold.

Chapters

0:00 Course Logistics: Midterm, Homework, and Project Check-ins

The clustering homework is due that day, with office hours immediately after class for questions.
The project intermediate report is due a couple of weeks after fall break and includes peer feedback plus a brief meeting with Jeff Phillips.
The streaming homework is planned for release by the end of the week or early during fall break.
The Thursday midterm allows a front-and-back reference sheet, but no calculators, computers, or phones.

8:35 Streaming Model: Summarizing an Ordered Sequence with Limited Memory

The input is an ordered stream a₁, a₂, …, aₘ, with each item drawn from a universe U.
A router receiving packets is the motivating example: it must summarize IP-address traffic without storing every packet.
The summary must update when a new item arrives and use space polynomial in log m and log |U|, rather than storing a counter for every universe element.

13:36 Frequency Queries and Why Exact Counts Are Too Expensive

For an item j, its frequency Fⱼ is the number of stream positions i for which aᵢ = j.
The task is to approximate frequencies for every possible item, such as every source or destination IP address.
Exact frequency tracking requires counters for all observed items and can consume space proportional to the number of distinct items.

16:48 Frequency Moments F₀, F₁, and F₂

F₀ counts distinct items with positive frequency; it is analogous to counting nonzero entries.
F₁ is the total number of stream items, equal to m, and is easy to maintain with one counter.
F₂ is the square root of the sum of squared item frequencies; it gives more weight to high-frequency items.
F₀ matters for measuring distinct users or customers, while F₁ and F₂ later help express approximation bounds.

21:54 Additive Frequency Approximation: Error εm for Every Item

The target estimate F̂ⱼ should satisfy |Fⱼ − F̂ⱼ| ≤ εm for every item j.
The parameter ε controls accuracy: smaller ε gives a tighter error bound but generally requires more memory.
Randomized methods also use δ, the probability that the stated guarantee fails.

25:45 Uniform Sampling for Frequency Estimation

Take K uniform samples from the stream, count sampled occurrences of j, then scale that count by m/K.
Uniform sampling remains valid even when the stream order is adversarial or bursty, provided the sample itself is uniform.
The sample count depends on ε and δ, not on m or |U|; storing each sampled item still requires space for its label.

33:40 Sampling Cost and the Majority-Item Warm-up

The sampling guarantee requires K on the order of ε⁻² log(1/δ), so 1% additive error takes roughly 10,000 samples before the failure-probability factor.
Items absent from the sample can be estimated as zero when their true counts remain within the allowed εm error.
Phillips introduces a simpler election-style task: return an item occurring more than m/2 times, if such a majority exists.

35:25 Boyer–Moore Majority Vote by Pairwise Cancellation

The majority algorithm stores one candidate label and one counter, initializing them from the first stream item.
A matching item increments the counter; a nonmatching item decrements it, and a negative counter replaces the candidate with the current item and resets the count to one.
The example stream uses small labels such as 2, 3, 4, 5, and 6 to illustrate how a candidate survives cancellations.

43:00 Misra–Gries: Tracking Multiple Frequent-Item Candidates

Misra–Gries generalizes the one-candidate method to K counters and K labels, initialized to zero and empty.
When an incoming item matches a label, increment its counter; when a label is empty, assign the item to it with count one.
If all labels are occupied and none matches, decrement every counter and clear labels whose counters reach zero.

49:00 Why Misra–Gries Decrements Every Counter

A nonmatching item cancels one occurrence from each tracked candidate, preventing any one candidate from receiving preferential treatment.
Decrementing only selected counters could leave stale high-count labels in place while repeatedly evicting newer candidates.
Each global decrement removes K units of accumulated counter mass, limiting how often the cancellation step can occur.

53:30 Misra–Gries Error Bound and Underestimation

For a query q, return its stored counter if q has a label; otherwise return zero.
The estimate never overcounts: F̂q ≤ Fq, because counters increase only when q actually appears.
At most m/K global-decrement events contribute error, giving 0 ≤ Fq − F̂q ≤ m/K.
Setting K = 1/ε yields additive error at most εm using about 1/ε labels and counters.

58:30 Misra–Gries Applications and Count-Min Sketch Trade-offs

A router can use roughly 100 Misra–Gries counters to identify traffic around 10% of the stream with about ±1% additive error.
Frequent destination IP addresses can reveal a distributed denial-of-service attack aimed at overwhelming one computer.
Misra–Gries is deterministic and compact but classically handles deletions less conveniently; its summary can depend on stream order.
Count-Min Sketch is randomized, supports deletions more naturally, and produces overestimates rather than Misra–Gries's underestimates.

1:03:10 Count-Min Sketch: Hash Rows and Counter Updates

Count-Min Sketch uses t independently randomized hash functions, each mapping items from the universe into a row of K counters.
Initialize every counter to zero; for each stream item, each hash function selects one counter in its row and that counter is incremented.
The sketch stores K × t counters, combining collisions so it avoids maintaining a separate counter for every item.

1:08:20 Count-Min Queries, Minimum Estimates, and Space

To query q, read the counter selected by q's hash in every row and return the minimum.
Every queried row counter is an overestimate because collisions can add counts from other items; taking the minimum gives the least overestimate.
Choosing K = 2/ε and t = log(1/δ) gives about (2/ε)log(1/δ) counters.
The stated guarantee is 0 ≤ F̂q − Fq ≤ εm with probability at least 1 − δ.

1:14:30 Count Sketch: Unbiased Estimates with F₂-Based Error

Count Sketch adds a sign hash that maps each item to +1 or −1, allowing counters to increase or decrease.
Colliding items cancel in expectation, making the resulting frequency estimates unbiased.
It aggregates estimates with a median rather than Count-Min's minimum and has error tied to F₂ rather than F₁.
The trade-off is a width on the order of 1/ε², with performance benefiting when the frequency distribution is skewed.

1:16:30 Apriori: Pruning Candidate Itemsets in Market-Basket Data

Apriori targets itemsets that co-occur in shopping receipts, using the classic—but not reliably true—diapers-and-beer example to motivate association analysis.
It first counts each individual item, then discards items below the support threshold before generating candidate pairs.
In the classroom receipt example, pairs are counted only among sufficiently frequent items; items 6 and 9 co-occur four times and meet the example threshold.
The same frequency-pruning principle can reduce candidate sets in other tasks, including graph algorithms that search for cliques.

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.