—

Stream Processing and Analytics

Window Concepts and Streaming Algorithms

Published: 2026-08-07

Level: postgraduate

Audience: Postgraduate students in stream processing and data engineering

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Tumbling windows — covered in Lecture 11
Sliding windows — covered in Lecture 11
Windows, trigger, and eviction policy — covered in Lecture 11
Streaming word count over a stream — covered in Lecture 11
Non-deterministic streaming algorithms — covered in Lecture 11
Random sampling — covered in Lecture 1

This session has two halves. The first half finishes the window concepts: batch intervals, tumbling windows, sliding windows, and session windows, each with a timing-diagram walkthrough and the business questions they answer. The second half opens the streaming algorithms topic: why these algorithms are probabilistic by nature, what concept drift is, and a full look at random sampling and reservoir sampling, including the algorithm's small-reservoir drawback and the modulo remedy for it.

The running thread is one question: when the data never stops arriving, how do you decide (a) when to compute, (b) how much data to compute over, and (c) how to compute correctly when you cannot store everything? The window types answer (a) and (b). The sampling algorithms answer (c).

12.1 Batch Interval: When the Algorithm Runs

Hook. A stream of events never stops. So how does a streaming system ever decide when to sit down and compute? The answer for almost every streaming engine is: it does not decide on its own — you hand it a clock. The batch interval is that clock.

12.1.1 Definition: The Trigger Interval

A batch interval is the specified time interval at which you trigger the algorithm. The class definition, in plain words: batch interval is basically the interval at which you trigger your algorithm; you are processing at some specified time interval. That is what "batch interval" means. If the batch interval is five minutes, you run your process every five minutes. The interval is set before processing begins, and every run of the algorithm happens on the events that have accumulated since the previous run.

Term on first use. A batch interval (the trigger interval), written $B$ , is the fixed time gap between two consecutive runs of your processing algorithm. If $B = 5$ minutes, the algorithm fires at 12:00, 12:05, 12:10, and so on, and each firing processes only the events that arrived after the previous firing.

Formal definition. Let $B$ (minutes, hours, or seconds) be the batch interval. The algorithm runs at times

$t_{0}, t_{0} + B, t_{0} + 2 B, t_{0} + 3 B, \dots$

where $t_{0}$ is the moment processing starts. At each run $t_{k} = t_{0} + k B$ , the algorithm processes exactly the events that arrived in the half-open interval $(t_{k - 1}, t_{k}]$ , meaning everything since the previous run, including anything that landed exactly on the boundary. This one quantity $B$ is the only decision the designer makes about when computation happens.

Intuition: the bakery's hourly tally. Imagine a bakery that counts how many customers walked in during each hour. Nobody stands at the door with a clicker watching the whole day; instead, at the top of every hour, someone looks at the receipts written since the last check. The "top of every hour" is the batch interval, and "receipts since the last check" is the data the run sees. The store never changes its checking schedule based on how busy it is — the schedule is fixed in advance, exactly like a batch interval.

The distinction matters because every window concept that follows is defined in terms of this one quantity. In a tumbling window the batch interval fully determines the window; in a sliding window the batch interval is only half the story. Before any of that, the timing axis of the day is built on it: 12:00, 12:05, 12:10, 12:15, and so on, with a run of the algorithm at each marked point.

Exam note: the batch interval definition — "the specified time interval at which you trigger the algorithm" — is a definition you must be able to state cleanly. Say it exactly in that shape: it is a specified, predefined time interval, and the algorithm is triggered at it.

12.1.2 Timing Diagram Basics

When the professor draws windows, the board shows a horizontal time axis with tick marks at each batch boundary, and events scattered between the ticks. Every example in this session is read off such a diagram: which events sit between 12:00 and 12:05, which batch run picks them up, and what happens at the next boundary. The same axis supports all three window types; the difference between the window types is only what the interval between two runs means.

Visual: picture the time axis as a number line with tick marks every five minutes:

12:00        12:05        12:10        12:15
  |-----E1 E2 E3-----|-----E4 E5-----|-----E6 E7-----|-->
      run #1            run #2          run #3

The horizontal axis is wall-clock time (minutes). The vertical event markers are scattered at their arrival times. At each tick mark a run of the algorithm fires. To read a window problem, always do the same three steps: (1) locate the event on the axis, (2) find which two tick marks bracket it, (3) report the run that picks it up. Both tumbling and sliding examples below are just this exercise with different bracket rules.

Scope and limits of the model. The timing diagram assumes the batch interval is fixed for the whole run and that every event carries a time that the system respects. Real engines add two wrinkles that this diagram hides: stream time (when the event enters the system) can differ from event time (when the event actually happened), and events can arrive late. The lecture model deliberately ignores both, so on the exam you read the diagram as drawn — events sit between the ticks that bracket them, period.

12.1.3 Student Questions and Answers

Q: Is the batch interval something that is predefined before the processing starts, or is it dynamic?

A: It is predefined. The batch interval is fixed before the processing starts and does not change while the stream runs. It is not something dynamic. If the run has already started, you cannot silently change the schedule — the boundaries were locked in before the first event was processed.

Recap + bridge. The batch interval is the heartbeat of a streaming pipeline: one fixed, pre-agreed trigger time $B$ , chosen before the stream starts. Every concept that follows takes this heartbeat and decides what data each heartbeat should look at — the tumbling window says "everything since the last beat," which makes $B$ the whole story. That is the next stop.

Real-world connection. Batch intervals are exactly what micro-batch engines use. In Spark Streaming and similar tools, the batch interval (often called the micro-batch duration, e.g. 1–10 seconds) decides how often a batch of streamed records is handed to the processing engine; it is the single knob that trades latency against throughput. Dashboards that refresh "every five minutes" and alert jobs that run "on the hour" are the same idea at human scale.

12.2 Tumbling Windows

Hook. "How much business activity in the last ten minutes?" — a question of this exact shape is behind half of all dashboard screens. The window type that answers it is the simplest one in stream processing, and it is fully decided by a single number you already know: the batch interval.

12.2.1 Definition: Window Size Equals Batch Interval

In a tumbling window, the size of the window is equal to the size of the batch interval. If the batch interval is five minutes, the window is five minutes wide, and there is no gap and no overlap between consecutive windows. Written out:

$W = B$

where $W$ is the window size and $B$ is the batch interval. Because the two are equal, the consequence is the defining property of the tumbling window: one event belongs to one window. An event that arrives inside the 12:00–12:05 window is processed exactly once, by exactly one batch, and never appears in any other window.

Why "tumbling". Picture a row of buckets on a conveyor, each exactly one batch interval wide, placed end to end with no space between them. The stream pours in; every event falls into exactly one bucket. When the clock reaches a boundary, the current bucket "tumbles" away to be processed and an empty bucket takes its place. There are no shared walls and no gaps — that physical image is the whole definition.

The name also connects to the standard framework vocabulary: stream processing engines call this a tumbling window (or fixed window), and two books in this course's reading list describe it the same way — a window of fixed length where every event belongs to exactly one window, typically implemented by rounding each event's timestamp to the nearest boundary. The professor's $W = B$ form and that description are the same statement.

The running process repeats as new events come in: at every batch boundary you clock the events that arrived since the previous boundary as a single batch, run the algorithm on it, and move on.

12.2.2 Worked Timing Example: Events E1 to E7

The worked example reads straight off the timing diagram. The batch interval is five minutes, so the axis is marked 12:00, 12:05, 12:10, 12:15. The events are scattered as follows:

E1, E2, E3 arrive between 12:00 and 12:05.
E4, E5 arrive between 12:05 and 12:10.
E6, E7 arrive between 12:10 and 12:15.

At 12:05 you run the algorithm. The events E1, E2, E3 are clocked as a single batch, and the processing algorithm runs on them. At 12:10 the next batch is E4, E5. At 12:15 the next batch is E6, E7. The process keeps repeating this way as new events arrive.

Worked walkthrough, step by step. Batch interval $B = 5$ minutes, processing starts at 12:00, so runs fire at 12:05, 12:10, 12:15.

Run at	Window covered	Events clocked as one batch	What the run processes
12:05	12:00–12:05	E1, E2, E3	the algorithm runs on {E1, E2, E3}
12:10	12:05–12:10	E4, E5	the algorithm runs on {E4, E5}
12:15	12:10–12:15	E6, E7	the algorithm runs on {E6, E7}

Sense-check: the three batches are disjoint (no event repeats) and together they cover every event (nothing is dropped). E4, E5 are in run 2 and only run 2; E6, E7 are in run 3 and only run 3. No event is ever counted twice and none is skipped — exactly the promise of a tumbling window.

The question the class was asked, and the point to remember: can an event be part of two particular batches in a tumbling window? The answer is no — that is the main point. Every event belongs to exactly one batch, so no event is ever processed twice.

Exam note: a timing-diagram walkthrough like this — given events and a batch interval, say which events are in which batch — is a likely question shape. The method is mechanical: bracket each event's arrival time between two boundaries, and report the later boundary's run. State the check "one event, one batch" out loud, because that is what the examiner is probing.

12.2.3 When to Use a Tumbling Window

The decision rule for choosing a tumbling window is about the shape of the business question. Whenever you want analytics of the form "how much data during the last N minutes", you use a tumbling window. The class examples:

How many orders were received in the last 10 minutes?
What is the maximum order among orders received in the last 10 minutes?
How much data has come in during the last five minutes?

If you can articulate a question from the business problem in that shape, the answer is a tumbling window. The window boundaries are fixed by the clock, which is exactly why a question phrased as "in the last ten minutes" maps onto it so cleanly.

Assumptions & scope. The tumbling window answers "how much in the last N minutes", not "how much across the last N minutes at every moment". Three assumptions come with it:

Clock alignment: boundaries are wall-clock times. "The last ten minutes" as a tumbling window means the ten-minute block that just ended at the boundary — if a question needs a truly rolling ten minutes that ends now, that is a sliding window, not a tumbling one.
No overlap tolerance: the answer is exact only when you accept that an event is counted in exactly one window. Dashboards that want each event counted once (order counts, totals) fit; questions that need smoothing or frequent refreshes do not.
Zero data is still a run: if no events arrive in a block, the boundary still fires and processes an empty batch. The clock does not wait for data.

Pitfalls. (1) Treating "last ten minutes" as a continuously moving span: a tumbling window only ever reports whole clock blocks, so a 12:00–12:10 question asked at 12:07 gets the 12:00 block, not the 12:07 block. (2) Expecting overlap: if your answer double-counts an event, you are no longer tumbling — that behavior belongs to the sliding window in the next section. (3) Forgetting the boundary rule: an event that lands exactly at 12:05 belongs to the new batch, not the old one; on the diagram it sits on the tick.

12.2.4 Student Questions and Answers

Q: Can an event be part of two particular batches in a tumbling window?

A: No. That is the main point of the tumbling window. One event belongs to exactly one window. An event is never shared between two batches. The window size equals the batch interval, and the windows sit end to end with no overlap, so there is no second home for any event.

Recap + bridge. Tumbling windows: $W = B$ , no gaps, no overlap, every event processed exactly once — the right tool for "orders in the last ten minutes" style questions. The bridge to the next concept: the moment a business question wants the answer refreshed more often than the window spans — a moving average, say — one number stops being enough. The sliding window adds a second time scale, and that is the next stop.

Real-world connection. Order volume dashboards and per-interval business metrics — "orders received in the last ten minutes", "maximum order value in the last ten minutes" — are the everyday uses of tumbling windows. E-commerce and payments systems emit such metrics per clock block, and frameworks such as Spark and Flink expose exactly this as a one-line windowed aggregation.

12.3 Sliding Windows

Hook. A trader wants to re-check the last ten minutes of prices every five minutes — not every ten. That is a question tumbling windows cannot even express, because it needs two clocks running at once. The sliding window is the window type built for exactly that two-clock situation.

12.3.1 Definition: Two Time Scales

The sliding window is the tool for moving averages. The key difference from the tumbling window: a sliding window has two time intervals, and they are not equal. The slide interval decides how often you repeat the process — how often you run the algorithm. The batch interval decides how much data you operate on — the span of data considered at each run.

The motivating example: you want to keep track of the top 10 transactions in a recent period. You repeat the process at a fixed cadence, and at each run you operate on the last portion of the data. Two time scales, different values. Another pair used in class: repeat the experiment every 30 minutes, and operate on the last 15 minutes of data. "Operate" here means perform some action — run the algorithm — on that span.

Formal definition. Let $S$ be the slide interval (how often the algorithm fires) and $B$ be the batch interval (how much recent data each firing looks at). Every $S$ minutes the algorithm runs, and when it runs it considers the events generated in the last $B$ minutes:

$fire at t_{0} + k S, consider [(t_{0} + k S) - B, t_{0} + k S]$

In the class example, $S = 5$ minutes and $B = 10$ minutes: every five minutes the algorithm runs, and each run considers the last ten minutes of data. Notice the two roles, so they cannot be confused: $S$ answers when, $B$ answers how much. A sliding window with $S = B$ degenerates into a tumbling window — the two clocks collapse into one.

Intuition: the moving spotlight. Imagine a flashlight fixed above a track that sweeps its beam along the rails every $S$ seconds, and the beam's width covers $B$ seconds of track. At every sweep, the beam lands on the most recent $B$ seconds of track — so it overlaps its own previous position, because it moved less than its width. That overlap is not a bug; it is the whole point of a sliding window, and it is why a moving average can be recomputed so often.

Term on first use. A moving average (a running average over the most recent data) is the canonical use: at every slide you re-average the last $B$ minutes of values, so the output line "slides" along with fresh data rather than jumping between fixed blocks.

12.3.2 Worked Timing Example: Slide 5 Minutes, Batch 10 Minutes

The timing diagram for the sliding window works like this. Slide interval is five minutes, batch interval is ten minutes, and processing started at 12:00. The trigger — the moment you fire the algorithm — happens every five minutes: 12:05, 12:10, 12:15, and so on.

At the 12:05 trigger, you consider data generated in the last ten minutes, which would be 11:55 to 12:05. But processing started at 12:00, so there is no data before 12:00. Only E1, E2, E3 are present, and the process runs on them.

At the 12:10 trigger, the last ten minutes is 12:00 to 12:10. The events in that span are E1 to E5 — and E6 as well, which arrives right at 12:10. So the run at 12:10 processes E1, E2, E3, E4, E5, E6.

At the 12:15 trigger, the last ten minutes is 12:05 to 12:15. The events in that span are E4, E5, E6, E7. So the run at 12:15 processes E4, E5, E6, E7. Note that E6 is in this window too — it was also in the previous run. The process repeats in this pattern, sliding along the time axis.

Worked walkthrough, step by step. $S = 5$ minutes, $B = 10$ minutes, start 12:00.

Trigger	The last $B = 10$ minutes =	Events inside the span	Events processed
12:05	11:55 – 12:05	only what exists since 12:00	E1, E2, E3
12:10	12:00 – 12:10	E1, E2, E3, E4, E5, E6	E1, E2, E3, E4, E5, E6
12:15	12:05 – 12:15	E4, E5, E6, E7	E4, E5, E6, E7

Each trigger slides the ten-minute span forward by five minutes, so consecutive runs share five minutes of history. Sense-check: the 12:15 run dropped E1, E2, E3 (they are older than ten minutes now) and kept E4, E5, E6 (they are inside 12:05–12:15) — the span is exactly as wide as $B$ at every trigger, never wider and never narrower.

Exam note: be ready to walk this timing diagram — given a slide interval and a batch interval, list the events in each trigger's window. The trap to avoid is the first trigger: the span would start before processing began, so clip it at the start time and count only events that actually exist. Work each trigger as its own row, exactly like the table above.

12.3.3 Overlapping Events

Can you expect overlapping events in a sliding window? Yes. Overlap means some events are processed more than once — they are reprocessed across micro-batches. In the example, E4 and E5 appear in the 12:10 run and again in the 12:15 run; E6 appears in both the 12:10 and 12:15 runs. That is the whole contrast with the tumbling window: in the tumbling case there are no common events between batches, while in the sliding case common events are normal and expected.

The overlap is deliberate, not wasteful. Because each run covers $B$ minutes of data but the slides advance only $S$ minutes, the older $B - S$ minutes of any run are exactly the newest $B - S$ minutes of the run before it. In the example, $B - S = 5$ minutes of every window repeat in the next one. The repetitions are what make a moving average smooth: the 12:15 average still reflects E4–E6, so the output changes gradually instead of restarting from scratch. The same property explains the memory cost: the engine must keep up to $B$ minutes of events alive between triggers.

Dimension	Tumbling window	Sliding window
Time intervals	one: $B$	two: $S$ (when to fire) and $B$ (how much data)
Window size vs batch interval	$W = B$	$B$ fixed, $S \leq B$ typically
Overlap between runs	none	normal — events reappear in later runs
Events processed per run	fresh events since last boundary	the most recent $B$ minutes, reprocessed
Best question shape	"how much in the last N minutes"	"moving average / top-K over a recent span"

When to pick which: if each event must be counted exactly once, use a tumbling window; if the answer must refresh more often than the data span and may re-read recent events, use a sliding window.

12.3.4 Real-World Use: Stock Market Analysis

The realistic home of the sliding window is stock market analysis. In the stock market you decide buy and sell in real time. What you do is observe the data for some period of time, wait for that period, then run the algorithm over a particular time interval of the data — exactly the two-time-scale pattern of the sliding window. The window slides because at every new trigger you re-examine the most recent span of prices and volume, which is what a moving average is: a decision function that re-runs on fresh data at a fixed cadence.

How it maps to the math. The trader's rule "buy when the 20-minute average crosses the 5-minute average" is two sliding windows running side by side: each fires every minute (small $S$ ) and each covers a different span (different $B$ ). The shorter window reacts to price moves quickly; the longer one is the trend line. When the two lines cross, the decision function fires. That is the lecture's "observe for a period, then run the algorithm over a particular interval" made concrete with real numbers.

Assumptions & scope. The sliding window's guarantees rest on two choices:

Slide ≤ batch. The example uses $S = 5$ , $B = 10$ . If the slide interval exceeds the batch interval, consecutive runs look at disjoint chunks of data — you are back to something like a tumbling window with gaps between blocks (see the Q&A below). The "moving average" reading only makes sense when the slide is fine enough that consecutive windows share data.
Memory scales with $B$ . The engine must hold up to $B$ minutes of events live between triggers. A long batch interval on a fast stream is a real memory bill; frameworks budget for it.

12.3.5 Student Questions and Answers

Q: Why do we want to operate on the last three hours of data?

A: The use case decides how much data you need. You will always have two time intervals. For example, you might repeat the process every six hours and operate on the last three hours of data — the top-10-transactions case. Or you repeat every 30 minutes and operate on the last 15 minutes. Any two intervals work; the numbers are a choice driven by the problem. There is no universal pair — the batch interval is set by how much history a decision needs, and the slide interval by how fresh the answer must stay.

Q: Could there be a case where the slide interval is greater than the batch interval?

A: That is allowed, but it will not give realistic answers, because you will have very few records in the window. The slide interval needs to be fine-tuned depending on the use case. If you slide every 30 minutes but only consider the last 15 minutes of data, each run sees only the newest 15 minutes — the data from the previous slide has already fallen out, so the "window" no longer overlaps or smooths anything.

Recap + bridge. The sliding window runs the algorithm every $S$ minutes over the last $B$ minutes of data, deliberately reprocessing overlapping events to feed moving averages. Both tumbling and sliding windows draw their boundaries from a fixed clock. The next window type abandons the clock entirely: the session window closes when the user goes quiet, not when a timer rings.

Real-world connection. Stock market analysis — moving-average style buy/sell signals are the textbook sliding window application. The same pattern runs network monitoring (traffic averages over the last five minutes, refreshed every 30 seconds), system metrics dashboards, and fraud scores that must track recent activity without re-reading the whole ledger.

12.4 Session Windows

Hook. A person opens a page, moves around a bit, then goes quiet for twenty minutes. When did their "visit" end? No clock can answer that — only the user's behavior can. The session window is the one window type whose boundary is decided by silence.

12.4.1 Definition: Windows Marked by Inactivity

The session window is the third window type, and it works on a different principle: there is no fixed boundary at all. You figure out some inactivity interval, and a session is marked by inactivity — the gap in the activity is called the inactivity duration. A session is a burst of events; the window closes when the user goes quiet.

Written out, with $Δ$ as the inactivity duration: the window stays open while consecutive events stay within $Δ$ of each other, and the window closes when the gap since the last event exceeds $Δ$ . The professor's phrasing — "you figure out some inactivity interval, and a session is marked by inactivity" — matches the standard definition in the stream processing literature: a session window groups the events of one user that occur closely together in time, and the window ends when the user has been inactive for some chosen period (for example, no events for 30 minutes). So the gap-exceeds- $Δ$ closing rule is the standard interpretation, and it is the one the exam expects.

Formal definition. Choose an inactivity duration $Δ$ (say $Δ = 30$ minutes). A session opens at the first event of an activity burst. Let $t_{j}$ be the arrival time of the latest event in the open session and let $t_{j + 1}$ be the time of the next event. The session stays open while

$t_{j + 1} - t_{j} \leq Δ$

and closes the moment the next event is so late that

$t_{j + 1} - t_{j} > Δ.$

Everything seen before that gap is one session; a later event after the gap opens a brand-new session. Unlike $B$ and $S$ , the value $Δ$ is not a computation schedule at all — it is a patience threshold: how long you wait before declaring a user gone.

Intuition: the group photo. A photographer asks everyone to hold still for the picture. People keep arriving; each new arrival resets the countdown. If someone arrives within $Δ$ seconds of the last arrival, they join the current photo. If the doorway stays empty for more than $Δ$ seconds, the photographer closes this photo and will start a new one for whoever shows up later. The photo — not the clock — ends when the arrivals stop coming. A session window is the same: it ends when the events stop coming, and only they can end it.

12.4.2 The Session Timeline Example

The timeline example in class: a user logs into a website at 12:00 and does nothing until 12:10 — no actions at all, just the page open. Then some activity happens, a few actions, and then silence again. Between the last activity and the next activity there is a stretch with no activity at all — the user has not generated any digital event in that stretch. That whole stretch, from the first activity to the inactivity gap, is one session. When the session ends, the window processing starts: you take all the events that were produced during that session and run your analysis on them as one unit.

Worked walkthrough. Let $Δ = 10$ minutes. Watch the stream of one user's events:

12:00 — user logs in. No events follow for a long stretch: the page is open but nothing is acted on. This empty stretch is the inactivity that begins the story.
12:10 — activity resumes (the user starts browsing). Events flow in quick succession: view page, follow a link, watch a video. As long as the gaps between events stay under 10 minutes, they all belong to the same session.
12:25 — an action arrives, 15 minutes after the previous one. Since $15 > Δ = 10$ , the session closes: everything from the first action after 12:10 up to 12:25 is one session.
The window processor now takes that whole burst — every event from that session — and runs the analysis on it as a single unit. A later event, whenever it arrives, opens a new session.

Sense-check: the session boundaries were decided entirely by the user's own rhythm (burst, then silence), never by a wall clock. If the same user had kept acting every two minutes, the session would still be open — the window does not know it is "supposed" to end.

12.4.3 Why Session Boundaries Are Unknown in Advance

The defining difficulty of the session window is that you never know when it is going to be closed, and you never know how long it is going to stretch. The intervals are not fixed — unlike the tumbling window, where the boundary is on the clock, or the sliding window, where the cadence is on the clock, the session window's boundary depends on the user's behavior, which you cannot predict. That unpredictability is precisely why the session window exists as a separate concept.

Assumptions & scope. The session window's usefulness depends on choosing $Δ$ well, and it lives on a data-shaped assumption:

The threshold is a business guess. $Δ$ is picked by the analyst — ten minutes for a news site, maybe an hour for a video platform. Too small a $Δ$ fragments one long visit into many tiny sessions; too large a $Δ$ merges two distinct visits into one. There is no right value except the one that matches how the product's users actually behave.
Events must be attributed to a user. Session logic only makes sense per user (or per device). If events arrive without a session key, there is no one whose silence can close a window — the whole concept needs the events grouped by actor first.

12.4.4 Real-World Use: Bot Detection on a Tax Website

The realistic use case the professor favored: phishing and bot detection. For example, somebody visits an income tax website, and you track all the activities — you are taking an audit trail of every action the user takes. A phishing script runs in bursts: sometimes it is active, sometimes it is inactive. When you track the activity and inactivity of the user's actions, the signature of a machine is the equal amount of gaps between the activities — the fixed, regular intervals give it away. A human pauses at random, with unequal gaps; a script produces a regular rhythm. The professor explicitly compared this with softer examples — searching on Amazon, watching a video on YouTube, coming back — and called those less tangible; the tax-website audit trail is the example where the session pattern actually separates a machine from a person.

Why the pattern works. Session windows hand the analyst a natural per-session shape: the sequence of gap lengths inside one session. A human's gaps scatter (1 min, then 40 seconds, then 7 minutes — pausing to read); a script's gaps are nearly constant (every 30 seconds, like clockwork). Constant gap lengths mean the "session" rhythm is mechanical, which is a strong machine signal. That is why the audit trail is the tangible case: the data is sparse enough that the rhythm stands out, whereas Amazon-style browsing is messy and mixed.

Pitfalls. (1) Treating "inactivity" as "no events arriving": a page left open produces no requests, but the user is still there — the window must react to the user's silence, not to the system's queue (see the Q&A below). (2) Expecting a session to close on a fixed schedule: it closes when the gap since the last event exceeds $Δ$ , which can happen at 12:03 for one user and 23:47 for another. (3) Picking one global $Δ$ for very different activities: a fraud-check session on a tax site and a video-watching session need different patience thresholds, because the underlying behaviors have different rhythms.

12.4.5 Student Questions and Answers

Q: What do we mean by inactivity?

A: Suppose a user logs into a website at 12:00 and does nothing until 12:10. No requests are received from the client to the server, and there is no action on the UI — the page is just open. That stretch is inactivity. The user is technically "present" (the tab is open) but generates no events, and that event-less stretch is what marks a possible session end.

Q: Does inactivity mean no events would be received?

A: It is not about events arriving. The event here is session tracking itself — you track whether the user generates any activity. The tracker watches for user actions, and inactivity is the measured absence of those actions, not a gap in the network feed.

Q: How does this tie into stream processing?

A: Every click on the website is an event in a stream of events. What counts as an event depends on the use case: it can be a timestamp, how much time the person spent reading a page, how long a link stays active, or what kind of content it has. The session tracker turns that stream into a stream of sessions, and the session window runs analytics on each burst of events as one unit — which is exactly how product analytics answers "how many sessions, how long, how many actions each".

Recap + bridge. Session windows have no fixed boundaries: pick an inactivity duration $Δ$ , keep a session open while event gaps stay under $Δ$ , close it when a gap exceeds $Δ$ , and process each burst as one unit. Unknown end times are the point, not a bug. This closes the window half of the lecture. The bridge to the second half: windows decide when and over what we compute — but computing over a never-ending stream forever is impossible, which is why the lecture now turns to streaming algorithms, starting with sampling.

Real-world connection. Phishing and bot detection on government websites via session activity patterns; e-commerce session analysis such as Amazon-style search-then-return sessions and YouTube viewing sessions. Web analytics products report sessions, session lengths, and bounce rates from exactly this window type, and Spark's streaming API implements it as a session window with a chosen inactivity gap.

12.5 Aggregation over an Unbounded Table

Hook. A stream never ends, but a table always has a "current contents". The bridge between the two — the idea that turned streaming into a database problem — is the unbounded table: treat the stream as a table that only ever grows, and every aggregation becomes a query that keeps re-running on it.

12.5.1 The Word Count Example

The window concepts close with a concrete aggregation demo that the professor walked through on the board. The model: an unbounded table — a table that only grows, with new records added at the end, never deleted. The events are words arriving as a stream: cat, dog, dog, dog.

When you run the count algorithm on this table you get the counts: cat appears 1 time, dog appears 3 times.

Formal picture. An unbounded table is a table with an ever-growing number of rows: rows are only added at the end, never updated in place and never deleted. Write the stream as rows landing in arrival order:

row 1	row 2	row 3	row 4	...
cat	dog	dog	dog	...

A count aggregation is a function of the whole table: for each distinct word $w$ , output

$count (w) = # {rows whose value is w}$

Here $count (cat) = 1$ and $count (dog) = 3$ . The table never shrinks, so no count is ever withdrawn — later runs can only add to a count, never subtract.

12.5.2 Incremental Counts as New Records Arrive

At $t = 2$ seconds, another message arrives carrying the words "verbal" and "cat". To the unbounded table, this new record gets appended. Now run the count algorithm again:

Step	Table contents	Counts after the run
Start	cat, dog, dog, dog	cat 1, dog 3
$t = 2$ s	+ verbal, cat	cat 2, dog 3, verbal 1
Next arrival	+ dog, verbal	cat 2, dog 4, verbal 2

Each run re-counts the whole table so far, and because the table is append-only, each new run's counts only grow the previous counts. The result of the first run is never corrected — it is extended. That is how aggregation actually happens over a stream: new records are appended, and the count algorithm is run again on the growing table.

Worked walkthrough, step by step. Start with the four-row table (cat, dog, dog, dog).

Run 1. Count the whole table: cat appears once, dog appears three times. Output: cat 1, dog 3.

At $t = 2$ seconds a new message arrives carrying "verbal" and "cat". Two rows are appended — the table now holds cat, dog, dog, dog, verbal, cat.

Run 2. Re-count the whole table: cat appears twice (row 1 and the new row), dog appears three times (unchanged — no dog arrived), verbal appears once. Output: cat 2, dog 3, verbal 1.

Next arrival. A message with "dog" and "verbal" is appended. The table holds cat, dog, dog, dog, verbal, cat, dog, verbal.

Run 3. Re-count: cat 2 (unchanged), dog 4 (one more dog), verbal 2 (one more verbal). Output: cat 2, dog 4, verbal 2.

Sense-check: every run's output equals the previous run's output plus the counts of the newly appended rows. Nothing from run 1 was ever revised — "cat 1" grew to "cat 2" by extension, never by correction. That monotone growth is the signature of aggregation over an append-only table.

12.5.3 Why This Is Stream Aggregation

The unbounded table is the mental model stream processing engines use: the stream is an append-only table, and every aggregation is a continuous query over it. With this demo the window concept portion of the course is complete, and the session moves to streaming algorithms.

The payoff of the model. Once you view the stream as an unbounded table, you can reuse everything databases already know: queries (the counts), indexes, joins, and the idea that a running aggregation is just a query that re-executes as rows arrive. Windowed aggregation from the earlier sections fits the same picture — a window is a slice of the unbounded table, and the window types decide which slice each run reads. The word-count demo is that model in miniature: no windows, no boundaries, just an ever-growing table and a query that keeps re-running.

Recap + bridge. The stream is an append-only table; each aggregation run re-counts the whole table so far, and results only grow. That completes the window concepts. The bridge to the second half is the catch in this demo: every run re-counted the whole table — which is only affordable because the table here is tiny. A real stream never ends, and re-reading everything every time is impossible. Streaming algorithms exist to get answers without that luxury, and they pay for it with probability — the next topic.

Real-world connection. Word-count-style aggregation over logs and message streams is the canonical example in stream processing platforms; the append-only-table model is how engines such as Spark structured streaming describe stream processing. Its API explicitly presents "the input stream as an unbounded input table", with every query compiled to a continuous query over it — the lecture's board demo is the exact conceptual model those engines implement.

12.6 Streaming Algorithms: An Overview

Hook. The stream is infinite, the memory is finite, and re-reading the whole table every time — as in the word-count demo — is off the table. Streaming algorithms are the compromise: algorithms that see each event once, keep only a small summary, and return answers that are probably right. This section explains why "probably" is unavoidable.

12.6.1 Four Families of Streaming Algorithms

The streaming algorithms topic covers a handful of algorithm families, and the class walks through them one by one:

Sampling algorithms — drawing a representative subset of the stream.
Membership — the presence or absence of an event in the window.
Frequency counting — counting events.
Most trending events — the "hot list".

The class covers the first family in detail (random sampling, then reservoir sampling). The remaining families — frequency counting, membership, and the trending hot list — are taken up in the next class; the professor deliberately stopped there because continuing would make the session too heavy.

The four questions. Each family answers one recurring question a stream user keeps asking:

Sampling: give me a small subset of the stream that stands in for the whole stream.
Membership: has this specific event been seen? (A test of presence, yes or no.)
Frequency counting: how many times has each value appeared?
Most trending events: which items appear most right now — the "hot list" of top items?

They share one constraint: the answer must be produced online, event by event, with memory far smaller than the stream.

12.6.2 Why Streaming Algorithms Are Non-Deterministic

All these algorithms are non-deterministic. The class was asked to think for a minute and say why. The opening guesses were on the right track but partial:

Sampling: how many of the events will be there in a window? It is not known — it is undeterministic.
Membership: whether an event is present or not in that window is uncertain.
Frequency counting: the counts are a moving thing.
Most trending events: the trend changes over time; the exact number may vary, and even the events themselves are arbitrary.

The full reason, stated directly: the events you consider are not the entire population. You are only collecting samples — if the window holds the whole stream, you would take every event; instead you take a sample of events from it. When you run an algorithm on these samples, the results are probabilistic in nature. That is why the approach is non-deterministic. It is not that you do a linear search over all n values — even when the algorithm itself is deterministic, the data it sees is a random selection.

Formalize the reason. Let $P$ be the whole population of stream events (too large to store) and let $S \subset P$ be the sample an algorithm actually sees. The algorithm computes a result

$θ^= f (S)$

on the sample. Since $S$ is a random selection, $θ^$ is a random variable: run the pipeline twice and $θ^$ may differ. The deterministic part — the function $f$ — does not remove the randomness; it only translates the randomness of the sample into a range of possible answers. If you could set $S = P$ , the answer would be exact — but that is precisely the case you cannot afford in streaming.

The class's own summary, confirmed as correct: when you are processing streaming data, you are not processing all the data, so the outcomes are not deterministic; your result depends on the samples that you have taken.

Exam note: expect to be asked why streaming algorithms are non-deterministic — the answer is that the data is sampled, not the full population, so results are probabilistic. Give the two-step structure: (1) memory forces sampling, (2) a sample is random, so every result computed on it inherits that randomness. A strong answer adds the contrast: the algorithm can still be deterministic — the data is the random part.

12.6.3 Concept Drift and Resource Constraints

The queries you want to run continuously are things like: how many elements are there, what is the most popular element, and similar questions. You keep running these queries over and over as the windows pass. Sometimes what happens is that the statistical data you observe in the first window is completely different from what you observe in the second window. That is called concept drift — the underlying distribution of the stream shifts between windows, so an algorithm tuned on the first window's statistics is looking at the wrong shape by the second window.

Formalize drift. Let $D_{1}, D_{2}, \dots$ be the statistical distributions of the stream as seen in window 1, window 2, and so on. Concept drift is the situation

$D_{k} \neq = D_{k - 1}$

— the distribution the stream is drawn from changes over time. Consequences: a model or threshold tuned to window 1's statistics (say, "normal traffic looks like this") silently mismatches window 2's data; counts, hot lists, and alerts built from old statistics drift away from reality. Continuous analytics must treat every statistic as provisional and rebuild it as the stream moves — which is exactly why the lecture stresses that counts are "a moving thing".

Beyond concept drift, there are resource constraints and domain constraints on streaming algorithms: memory and time budgets that force the sampling and approximation in the first place. The memory budget is the fundamental one — a finite machine cannot hold an unbounded stream, so every streaming algorithm must compress what it sees into a bounded summary. Time budgets matter too: an event arrives, and the algorithm has only the instant between arrivals to update its summary. Domain constraints are the business ones — for example, a regulator may require certain records kept for months, which shapes what can be summarized versus what must be stored whole.

Pitfalls. (1) Treating a streaming answer as exact: because the data is sampled, a reported count or top list is an estimate with randomness around the true value. (2) Tuning parameters on one window and never re-checking: concept drift makes static tuning age badly — a fraud threshold tuned on January's stream misreads February's. (3) Confusing "the algorithm is deterministic" with "the answer is exact": determinism of $f$ does nothing about the randomness of the sample $S$ . (4) Ignoring the time budget: an algorithm that cannot finish between two consecutive arrivals falls behind forever, since the stream does not wait.

Recap + bridge. Streaming algorithms work on samples, so their answers are probabilistic; the stream's distribution shifts (concept drift), so even good answers go stale; and memory, time, and domain limits are the reasons sampling exists at all. The next sections make this concrete: random sampling (equal chance for every event) and reservoir sampling (maintaining a random sample online without storing the stream).

Real-world connection. Concept drift is the standing problem in continuously running analytics — recommendation statistics, fraud thresholds, and monitoring baselines all drift as the stream's behavior changes. Fraud systems re-train thresholds on rolling windows for this reason, and monitoring platforms continually re-baseline "normal" because yesterday's normal is not today's.

12.7 Random Sampling

Hook. The fairest way to pick one person out of a crowd: write every name on a slip, put the slips in a hat, and draw one. Random sampling is that hat, applied to a window of stream events — with one catch: the hat must be built from a sample, never from the whole population.

12.7.1 Equal Probability for Every Element

Random sampling is the simplest sampling idea: each element is given equal probability to get picked up as part of that particular window. For a window with $n$ elements, the chance any specific element is selected is:

$\frac{1}{n}$

The professor's wording: you say that each element is having equal probability to get picked up as part of that window. That is the entire contract of random sampling — no element is favored over any other.

Formal definition. Let the window hold $n$ elements, indexed $e_{1}, e_{2}, \dots, e_{n}$ . A random sample is any selection rule under which every element has the same chance of being chosen:

$P (e_{i} selected) = \frac{1}{n} for every i = 1, \dots, n$

and the selection of one element does not bias the selection of any other. That single equality is the whole definition — nothing else is claimed. The probability depends only on $n$ , the window's size, so the contract holds automatically as long as all $n$ candidates are in play.

Why the probability is $1/ n$ and not something else. Probabilities in one window sum to 1 over the candidates: if one element had a higher chance, some other element would have to drop below $1/ n$ to compensate — the "no favorite" rule forbids exactly that. So the only fair value for $n$ candidates is $1/ n$ each. That is why the professor's statement "equal probability to get picked up" is immediately "chance $= 1/ n$ ": the two are the same sentence in math.

Worked example. A window holds $n = 5$ events: E1, E2, E3, E4, E5. Each event's chance of being the pick is

$P (E_{i}) = \frac{1}{5} = 0.2 (i = 1, \dots, 5)$

If the window later grows to $n = 10$ events, every chance drops to $1/10 = 0.1$ . Sense-check: the five individual probabilities add up to $5 \times 0.2 = 1$ , as a proper probability spread over five candidates must. The bigger the window, the smaller each equal share — that is the honest trade of random sampling.

Assumptions & scope. The $1/ n$ contract holds only while three conditions hold:

All candidates are known up front. To give every element an equal chance you must be able to see (or draw from) the whole window of $n$ elements. On a stream, that means the window must be a stored, bounded set — you cannot know $n$ while the stream is still flowing and unbounded.
Sampling is fair by construction. The $1/ n$ is about the selection rule, not the stream. If the data itself is biased (rare values cluster in certain time slots), random sampling of events does not remove that bias — it preserves it.
Fresh selection per question. The professor's contrast, stated below, is important: random sampling picks a fresh random selection each time; it keeps no memory across runs.

Pitfalls. (1) Writing $1/ n$ when the window size is unknown: on a live stream $n$ is a moving target, and a formula with a phantom $n$ promises an equality the algorithm cannot honor. (2) Confusing "each element has the same chance" with "the sample contains one of everything": equal chance means equal probability of selection, not proportional representation — two events may still be picked and one may not. (3) Assuming a second run repeats the first: each run is an independent fresh selection, so the picked set changes every time.

Recap + bridge. Random sampling assigns every element of a known $n$ -element window the equal chance $1/ n$ , with no favorites. Its limitation is the setup itself: you must know the whole window before you can be fair. The bridge to the next concept: what if the window is the entire infinite stream — when do you ever get to see all $n$ candidates? Reservoir sampling is the algorithm that maintains the same $1/ n$ fairness online, element by element, without ever knowing $n$ in advance.

Real-world connection. Random sampling is the workhorse for monitoring and profiling: sampling network packets to estimate traffic mix, sampling clicks to estimate feature usage, and sampling logs for anomaly triage all use an equal-chance pick per window. The estimates it produces inherit the $1/ n$ fairness — which is why it is trusted where every record "should" be equally visible, and why production systems replace it with reservoir sampling the moment the data stops fitting in memory.

12.8 Reservoir Sampling

Hook. Random sampling needs the whole window before it can be fair — but on an infinite stream, the whole window never exists. Reservoir sampling solves this: it keeps a running random sample online, updating it as each event flows past, and the sample stays just as fair as a fresh draw from a hat — without ever storing the hat.

12.8.1 The Algorithm

Reservoir sampling means that you maintain a random sample online, and you define some sample size $K$ , called the reservoir size. The insight: if $K = 1$ , you are putting one element in the reservoir, and that element — taken from the stream — can be any one of the $n$ elements, so each element's chance of being the one is $\frac{1}{n}$ .

The algorithm, step by step. Let $S$ be the stream of values and $K$ the reservoir size:

Insert the first $K$ elements into the reservoir. If the stream is indexed 1 to $K$ and then $K + 1$ to infinity, the reservoir $R$ of size $K$ is filled with $S (1)$ up to $S (K)$ .
For each remaining value in the stream, let $i$ be the position of that value (the element $E_{i}$ at position $i$ ).
Run a random number generator to get a random number $M$ between 1 and $i$ .
If $M$ is within 1 to $K$ , replace the element at that particular position in the reservoir with the new element.

Written out:

$M \sim Uniform {1, 2, \dots, i}$

$if M \leq K then R [M] \leftarrow S [i]$

The professor's verbal description, kept next to the math: "I will run a random number generator here. Get random between 1 to I. If that index is within 1 to K, then I am replacing the element at that particular position with a new element." The name for this procedure: random reservoir sampling, because every replacement is driven by a random index.

Purpose and mechanics. The problem: draw a fair sample of size $K$ from a stream of unknown length $n$ , using memory $O (K)$ , seeing each event once. The procedure, unpacked:

Inputs: the stream $S$ (unknown length), the reservoir size $K$ , and a source of uniform random integers.
Output: at every moment, a reservoir $R$ of exactly $K$ elements that is a uniformly random $K$ -subset of everything seen so far.
Why it is fair: an element at position $i$ enters the reservoir with probability $K / i$ (its draw $M$ must land in $1.. K$ ), and once inside it survives each later step with the right probability to cancel out — the same mathematics that makes Algorithm R (the standard name in the literature, e.g. Knuth's formulation) produce a uniform sample. The $K = 1$ case makes the fairness visible: with one slot, the element currently in the reservoir is equally likely to be any of the $n$ elements seen so far, which is exactly the $\frac{1}{n}$ contract of random sampling.

Symbols: $S$ — the stream; $S (i)$ or $E_{i}$ — the element at position $i$ ; $K$ — the reservoir size; $R$ — the reservoir array, $R [1.. K]$ ; $M$ — the random draw for the current element, uniform over $1, \dots, i$ .

Intuition: the bouncer's guest list. A club has $K$ seats saved at the front. The first $K$ guests just sit down. Every guest after that rolls a die with a growing number of faces: for guest number $i$ , the die has $i$ faces. If the die shows a number within the first $K$ , that seat's current occupant is asked to leave and the new guest takes the seat. Most guests with big numbers will roll past $K$ and simply walk on — the list turns over, but slowly, and at every instant the $K$ names on the list are a fair cross-section of everyone who arrived. The die is the only thing the club needs; it never has to count the whole queue.

12.8.2 Worked Example: Reservoir of Size 3

The worked example runs on a concrete stream. The positions are 1 to 10, and the stream is:

$S = A, B, C, P, Q, R, Alpha, Beta, Gamma, Delta$

The reservoir size is 3, so the first step copies the first 3 elements: $R = A, B, C$ . From now on the algorithm looks only at the remaining elements, $P, Q, R, Alpha, Beta, Gamma, Delta$ , at positions 4 to 10.

Next, run the random number generator for the element $P$ at position 4: get a random number between 1 and 4, which can be 1, 2, 3, or 4. Suppose it returns 2. Since 2 is within 1 to 3, replace the second element of the reservoir: the reservoir becomes

$R = A, P, C$

Why $P$ and not $Q$ or $R$ ? Because the algorithm goes through the remaining stream one element at a time, and $P$ is the very next element, at position 4 — the upper bound of the random draw is 4, matching P's position.

Next time the algorithm runs, the draw is between 1 and 5 for the element at position 5. If the random number comes out greater than the reservoir size — 4 or 5 — nothing happens: the reservoir is left untouched. If it comes out 1, 2, or 3, the element at that index is replaced with the current stream element. And so on through the rest of the stream: Alpha, Beta, Gamma, Delta each get a draw against an upper bound that grows by one every step.

Worked walkthrough, step by step. $K = 3$ ; stream $A, B, C, P, Q, R, Alpha, Beta, Gamma, Delta$ at positions 1–10.

Position $i$	Element	Draw $M$ (this run)	Action	Reservoir after
1–3	A, B, C	— (fill phase)	copy first $K$ elements	A, B, C
4	P	2	$2 \leq 3$ , replace $R [2]$	A, P, C
5	Q	4	$4 > 3$ , do nothing	A, P, C
6	R	1	$1 \leq 3$ , replace $R [1]$	R, P, C
7	Alpha	5	$5 > 3$ , do nothing	R, P, C
8	Beta	3	$3 \leq 3$ , replace $R [3]$	R, P, Beta
9	Gamma	7	$7 > 3$ , do nothing	R, P, Beta
10	Delta	2	$2 \leq 3$ , replace $R [2]$	R, Delta, Beta

Final reservoir: $R =$ R, Delta, Beta. Sense-check: the reservoir is always exactly $K = 3$ elements; each new element either takes a seat (draw $\leq 3$ ) or walks on (draw $> 3$ ); and the chance of a seat drops as $i$ grows — at position 4 the chance was $3/4$ , at position 10 it is $3/10$ . The exact draws above are one coin-flip outcome; a different run's draws would produce a different — but equally fair — reservoir.

Q: Why is P replacing B, and not Q or R?

A: Because P is the very next element at position 4, and the random number was drawn between 1 and 4. Each element of the remaining stream is considered one at a time. Q and R are still in the future — their positions are 5 and 6 — and they have not had their draws yet, so they cannot be the ones swapping in.

12.8.3 The Small-Reservoir Drawback

What is the end result of the algorithm? Every time, the reservoir holds a random sample from the stream. You run the experiment, then you fill the reservoir again with new random indices, and you keep generating new sample sets.

The drawback surfaces when you ask: how many times must I run to get a new sample set? It can happen that after several runs the reservoir may remain unchanged. Why? If the random number is greater than the reservoir size every time, the algorithm does nothing — no element is replaced. The probability problem: when the reservoir size is small, the random index is very likely to fall outside the range 1 to $K$ , so you may never get an update. If the reservoir size is substantially large, there is no problem; the small-reservoir case is where the algorithm stalls. That is the professor's warning, in his own framing: "If the reservoir size is small, nowhere you get a chance to update the reservoir, because the index value is very likely that you get is outside the bounds of your reservoir index."

The stall, quantified. At position $i$ , the draw $M$ is uniform over $1, \dots, i$ , so the probability that an element actually enters the reservoir is

$P (M \leq K) = \frac{K}{i}$

with $K$ the reservoir size. For $K = 3$ : at position 10 the chance of an update is $3/10 = 0.3$ (30%); at position 100 it is $3/100 = 0.03$ (3%); at position 1000 it is $3/1000 = 0.003$ (0.3%). The larger $i$ gets, the rarer the updates become — and with a small $K$ that happens much sooner. Run the algorithm a handful of times at a large position and the draws keep landing outside $1.. K$ , so the reservoir stays exactly the same. A large reservoir escapes the problem because $K / i$ stays substantial much longer — with $K = 1000$ , even at position 10000 the update chance is still 10%.

12.8.4 The Modulo Remedy

The remedy discussed in class: apply the modulo operator to the random number. If $M$ is greater than $K$ , take $M mod K$ — the remainder of the division is always inside 1 to $K$ . In the example, if the random number is more than 3, then 4 modulo 3 is 1, so the first element of the reservoir would be replaced:

$M^{'} = {M M mod K M \leq K M > K$

The professor accepted any transformation that keeps the index within the reservoir size — a student suggested an alias-style condition, and the reply was that any transformation is fine. The only caution: look at the variant carefully, especially when the reservoir size is small; with a large reservoir the plain algorithm already works.

Why the remainder is always in range. The modulo operation divides $M$ by $K$ and keeps the remainder: $M mod K$ lies in ${0, 1, \dots, K - 1}$ , and mapping the 0 remainder back to $K$ (or treating the reservoir as 0-indexed, as the class example does by calling $4 mod 3 = 1$ the first slot) guarantees a valid position. The transformation's only job is to turn an out-of-range draw into an in-range one so that the algorithm always has a chance to update. Any other mapping with the same guarantee — the student's alias-style condition included — is equally acceptable to the professor; what matters is that the variant is checked carefully, because the remap can change the sampling's fairness when the reservoir is small.

Exam note: the small-reservoir drawback and the modulo remedy are the classic follow-up pair on a reservoir sampling question — expect the "you may never get an update" trap and the modulo fix. State the trap with the probability: at position $i$ the update chance is $K / i$ , so a small $K$ at a large position makes updates rare. State the fix in one line: remap the draw $M > K$ to $M mod K$ so the index always lands inside the reservoir.

12.8.5 Student Questions and Answers

Q: What will be the end result of the reservoir?

A: Every time, the reservoir holds a random sample from the stream. You run the experiment, then you fill the reservoir again with new random indices, so you keep generating new sample sets. The reservoir is never a fixed answer — each fresh run over the same stream yields a new, equally fair sample.

Q: It may happen that running three or four times, the reservoir is not changed at all. Is that possible?

A: Correct. If the random number is greater than the reservoir size every time, you do nothing, and the reservoir stays exactly the same. You only replace an element when the random number falls between 1 and K. As the position $i$ grows, the chance $K / i$ of falling in range shrinks, so unchanged reservoirs become the rule rather than the exception for small $K$ .

Q: What is the remedy when the random number keeps falling beyond the reservoir?

A: Apply the modulo operator. If M is greater than K, take M modulo K, and the remainder is always inside 1 to K. In the example, 4 modulo 3 gives a remainder of 1, so the first element would be replaced. Any transformation that guarantees the index stays within the reservoir size works — the professor accepted a student's alias-style condition as fine — but you need to look at the variant carefully when the reservoir size is small, because the remap can change which elements the reservoir favors.

Q: Once the reservoir is full with the first K elements, will the random number always be higher than K?

A: If the random number is greater than K, you need some mechanism to handle it. Otherwise you are happy and simply do nothing. There is no guarantee either way: the draw is uniform over 1 to $i$ , so it can be as small as 1 or as large as $i$ ; the reservoir updates only when the draw lands inside 1 to K, and that is the entire decision.

Q: The instance removed and the instance inserted do not seem to be at the same index. Is that right?

A: The index depends on the random number M. You replace the element at index M with the current stream element, so the position and the replacement go together: the incoming element takes the exact seat that the random draw named, and the occupant of that seat — whichever element it is — is the one removed.

Recap + bridge. Reservoir sampling maintains a running random sample of size $K$ : fill with the first $K$ elements, then for every later element at position $i$ draw $M$ uniformly from $1.. i$ and replace $R [M]$ when $M \leq K$ . Its fairness matches random sampling's $1/ n$ contract without storing the stream, but a small reservoir can stall because updates are rare; the modulo remap forces every draw inside range. This closes the sampling family. The next class continues the remaining families — frequency counting, membership, and the trending hot list — which solve the same memory problem with the same probabilistic compromise.

Real-world connection. Reservoir sampling is the standard way to keep an online random sample: ad networks sample served impressions for auditing, telemetry systems keep a running sample of metrics for post-hoc analysis, and databases use it for unbiased statistics over tables too large to scan. Spark and other frameworks provide reservoir-sampling utilities precisely because a stored full population is usually unavailable — the same reason this lecture singles the algorithm out for exam treatment.

Exam Guidance Summary

Exam note — quiz scope. Quiz two covers everything taught from the mid-sem exam until the last class. Quizzes are not exams: their purpose is to assess your understanding of the regular classes and the concepts covered. If you attend classes regularly, whatever was explained should be enough — you do not need to prepare as if it were a major exam, and you should not procrastinate.

Q: What is the syllabus for quiz two?

A: Everything covered from the mid-sem exam until the last class. The quiz is not an exam; it assesses your understanding of the regular classes and the concepts covered. Attending regularly is enough — you do not need to prepare as if it were a major exam, and you should not procrastinate.

Batch interval: be able to state the definition cleanly — the specified, predefined time interval at which the algorithm is triggered; fixed before processing starts, not dynamic.
Tumbling windows: questions ask how many orders were received in the last ten minutes, or the maximum order in that span; the window size equals the batch interval, and no event belongs to two batches. Be ready to read a timing diagram and assign events to batches.
Sliding windows: used for moving average questions with a slide interval and a batch interval; be ready to walk a timing diagram and list the events in each trigger's window, clipping the first window at the processing start time.
Session windows: close after inactivity; you never know when a session will end or how long it stretches. Know the inactivity-duration $Δ$ rule: the window closes when the gap since the last event exceeds $Δ$ .
Streaming algorithms: expect to explain why the algorithms are non-deterministic and probabilistic in nature — the data is sampled, not the whole population, so results are probabilistic; also expect concept drift, the shift in the stream's distribution between windows.
Reservoir sampling: expect the algorithm, its drawback for small reservoirs (the random index often falls outside 1 to K, so the reservoir never updates — probability $K / i$ of an update at position $i$ ), and the modulo remedy ( $M mod K$ maps the draw back inside 1 to K).

Key Industry Applications

Tumbling windows: order volume dashboards — orders received in the last ten minutes, maximum order value in the last ten minutes. The fixed clock blocks make these metrics easy to compare hour over hour and day over day.
Sliding windows: stock market analysis — real-time buy and sell decisions driven by moving-average style re-runs over recent data. The same two-time-scale pattern runs network traffic averages, monitoring dashboards, and fraud scores that must track recent activity.
Session windows: phishing and bot detection on government websites (the income tax website audit trail), where the equal gaps between a script's activities expose a machine; e-commerce session tracking such as Amazon-style search-then-return and YouTube viewing sessions.
Aggregation over an unbounded table: word-count-style analytics over logs and message streams; the append-only-table model is how stream processing engines such as Spark structured streaming describe the stream — the input is treated as an unbounded table and every query becomes a continuous query.
Streaming algorithms: hot lists such as trending topics; concept drift is the standing problem in continuously running analytics — fraud thresholds, recommendation statistics, and monitoring baselines all drift with the stream.
Reservoir sampling: online random sampling wherever the full population cannot be stored — ad-impression auditing, telemetry sampling, and database statistics over huge tables all keep a running sample of bounded size.

SPA Lecture 12 notes · Window Concepts and Streaming Algorithms

Stream Processing and Analytics· postgraduate· 2026-08-07

Sections Breakdown

112.1 Batch Interval: When the Algorithm Runs

The fixed time interval at which a streaming algorithm is triggered.

212.2 Tumbling Windows

Window size equals the batch interval: no gaps, no overlap, one event belongs to one window.

312.3 Sliding Windows

Two time scales — the slide interval and the batch interval — powering moving averages.

412.4 Session Windows

Windows marked by inactivity: a session closes when the gap since the last event exceeds the inactivity duration.

512.5 Aggregation over an Unbounded Table

The stream as an append-only table with continuously re-run count queries.

612.6 Streaming Algorithms: An Overview

Why streaming algorithms are non-deterministic and what concept drift is.

712.7 Random Sampling

Equal probability 1/n for every element of the window.

812.8 Reservoir Sampling

Maintaining a fair random sample online; the small-reservoir drawback and the modulo remedy.

9Exam Guidance Summary

Quiz scope and per-topic exam guidance from the lecture.

10Key Industry Applications

Real-world uses of each window type and sampling algorithm.

Postgraduate students in stream processing and data engineering

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

Batch Interval: When the Algorithm Runs

Must-know: The batch interval is the specified, predefined time interval at which you trigger the algorithm; it is fixed before processing starts and never changes while the stream runs.

$t_{0}, t_{0} + B, t_{0} + 2 B, \dots$

⚠️ Top pitfall: Treating the batch interval as dynamic — it is predefined and fixed before processing begins.

Self-check: If the batch interval is five minutes and processing starts at 12:00, when does the second run fire?

Connects to: Tumbling Windows

Tumbling Windows

Must-know: Tumbling window: window size equals the batch interval; no gaps, no overlap; one event belongs to exactly one window and is never processed twice.

$W = B$

⚠️ Top pitfall: Expecting overlap between consecutive batches — in a tumbling window no event is ever shared between two batches.

Self-check: With a five-minute batch interval and events E1,E2,E3 between 12:00 and 12:05, which events does the 12:05 run process?

Connects to: Batch Interval, Sliding Windows

Sliding Windows

Must-know: Sliding window has two time scales: the slide interval S (how often the algorithm runs) and the batch interval B (how much recent data each run considers); overlap between runs is normal and expected.

$fire at t_{0} + k S, consider [(t_{0} + k S) - B, t_{0} + k S]$

⚠️ Top pitfall: A slide interval larger than the batch interval gives very few records in the window and unrealistic answers.

Self-check: With S = 5 min and B = 10 min starting at 12:00, which events does the 12:15 trigger process?

Connects to: Tumbling Windows, Session Windows

Session Windows

Must-know: Session windows close after inactivity: pick an inactivity duration Delta, keep the window open while event gaps stay under Delta, and close it when a gap exceeds Delta; boundaries depend on user behavior, never on a clock.

$t_{j + 1} - t_{j} > Δ \Rightarrow session closes$

⚠️ Top pitfall: Interpreting inactivity as 'no events arriving' — inactivity is the user generating no activity; a page left open is inactivity even though the connection lives.

Self-check: What reveals a phishing script in a session activity audit trail?

Connects to: Sliding Windows, Aggregation over an Unbounded Table

Aggregation over an Unbounded Table

Must-know: A stream is an unbounded, append-only table; every aggregation is a continuous query re-run on the growing table, and earlier results are extended, never corrected.

$count (w) = # {rows whose value is w}$

⚠️ Top pitfall: Thinking an earlier count gets revised — results only grow as new records are appended.

Self-check: After appending 'dog, verbal' to cat, dog, dog, dog, verbal, cat, what are the counts?

Connects to: Streaming Algorithms

Streaming Algorithms: An Overview

Must-know: Streaming algorithms are non-deterministic because the data is sampled, not the whole population, so results are probabilistic; concept drift is the stream's distribution shifting between windows.

$θ^= f (S), S \subset P$

⚠️ Top pitfall: Claiming the algorithm itself is random — the algorithm can be deterministic; the sample it sees is the random part.

Self-check: Why are the results of streaming algorithms probabilistic in nature?

Connects to: Aggregation over an Unbounded Table, Random Sampling, Reservoir Sampling

Random Sampling

Must-know: Random sampling: each element of the window has equal probability 1/n of being picked; the contract is no element is favored.

$P (e_{i} selected) = \frac{1}{n}$

⚠️ Top pitfall: Using 1/n when the window size is unknown — on a live stream n is a moving target and the equality cannot be honored.

Self-check: If a window holds 5 events, what is the probability any specific event is picked?

Connects to: Reservoir Sampling

Reservoir Sampling

Must-know: Reservoir sampling: fill the reservoir R with the first K elements; for each element at position i draw M uniformly from 1..i and replace R[M] if M <= K. Drawback: with a small reservoir the draw is likely to fall outside 1..K so the reservoir never updates; remedy: apply modulo so M' = M mod K stays in range.

$M \sim Uniform {1, 2, \dots, i}, if M \leq K then R [M] \leftarrow S [i]$

⚠️ Top pitfall: Small reservoir, no updates: at position i the update chance is K/i, so with a small K the random index is very likely outside 1..K and the reservoir remains unchanged.

Self-check: For reservoir size 3 and stream A,B,C,P,Q,R,..., if the draw for P (position 4) is 2, what is the reservoir after processing P?

Connects to: Random Sampling, Streaming Algorithms

Previous LectureLecture 11 · Spark Structured Streaming: Word Counts, Output Modes, and Windows

Next LectureLecture 13 · Streaming Algorithms: Decaying Window and Membership

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.