Stream concepts, the stream data model and architecture, stream computing, sampling and Bloom filters.
A data stream arrives continuously and too fast to store, so it must be analysed in a single pass with limited memory. Every algorithm for streams therefore trades exact answers for fast, approximate ones whose error can be bounded. This chapter (the first half of syllabus Unit III) introduces stream concepts, the stream data model and architecture, stream computing, sampling and filtering; Chapter 8 covers counting, moments, windows, real-time platforms and case studies.
7.1 Introduction to stream concepts
A data stream is a continuous, ordered and potentially unbounded sequence of data items that arrive in real time. Examples include sensor readings from machines, packets crossing a network, clicks on a website, posts on social media, card transactions and stock-market ticks. Stream data differs from stored data in almost every respect. A stored database is finite and can be read many times in any order, and queries return exact answers. A stream is unbounded and arrives at high speed; it can usually be read only once, in arrival order; only a small summary or recent window can be kept in memory; queries run continuously rather than once; and answers are often approximate. Stream processing also faces concept drift — the statistical properties of the data change over time, so a pattern learned last month may no longer hold.
| Basis | Traditional (stored) data | Data stream |
|---|---|---|
| Size | Finite, known | Unbounded, unknown |
| Access | Random, many passes | Sequential, usually one pass |
| Arrival | Data at rest | Data in motion, at high speed |
| Storage | Fully stored on disk | Only a summary or window in memory |
| Answers | Exact | Approximate, with error bounds |
| Queries | One-time (ad hoc) | Continuous (standing) |
Worked example – why streams cannot simply be stored. A payment network handles 10,000 transactions per second, each 1 KB in size.
- Data per second = 10,000 × 1 KB = 10 MB.
- Data per day = 10 MB × 86,400 = 864,000 MB ≈ 864 GB.
- Data per week ≈ 864 GB × 7 ≈ 6 TB.
- A fraud check must answer within a fraction of a second. Scanning even one day's 864 GB at 1 GB/s would take 864 s, about 14 minutes — far too slow. The system must keep compact summaries in memory and update them as each transaction arrives.
7.2 Stream data model and architecture
A Data Stream Management System (DSMS) processes streams the way a database management system processes tables. One or more input streams enter the system, each at its own rate and with its own data type, and are handled by a stream processor. Users register standing queries in advance, which run permanently and produce results whenever new data arrives — for example, "alert whenever a furnace temperature exceeds 1,500 °C". Users can also ask ad-hoc queries, one-time questions about the current state of the stream; these can only be answered if the system has kept suitable summaries. The processor keeps those summaries, samples and recent windows in a limited working storage (main memory or fast disk). The full stream may be written to archival storage, which is large but too slow to be used for answering queries in real time. Results leave the system as output streams to dashboards, alerts or other systems.
Streams enter on the left and are read once by the processor, which answers standing and ad-hoc queries from the summaries kept in working storage; the archive (dashed) keeps raw data for later, not for live answers.
Sliding windows. Because a stream never ends, many queries are asked over only its most recent part, called a sliding window. A count-based window holds the last N elements; a time-based window holds the elements that arrived in the last t time units. As each new element arrives, the oldest one leaves the window, and summaries such as sums can be updated incrementally instead of being recomputed.
Worked example – a count-based sliding window. The stream is 3, 7, 2, 9, 4, 6, 1 and the window size is N = 5.
- After 5 elements the window is [3, 7, 2, 9, 4]; sum = 25, average = 25 / 5 = 5.0.
- When 6 arrives, 3 leaves: new sum = 25 − 3 + 6 = 28 (no need to re-add all five); window [7, 2, 9, 4, 6], average = 5.6.
- When 1 arrives, 7 leaves: new sum = 28 − 7 + 1 = 22; window [2, 9, 4, 6, 1], average = 4.4.
- Each update costs one subtraction and one addition, however large N is.
7.3 Stream computing
Stream computing (stream processing) is a style of computation that processes each data item as soon as it arrives, rather than storing data first and processing it later in large batches. An application is built as a data-flow graph of operators — filter, map, aggregate, join — connected by streams, and the graph is spread over many machines so that operators run in parallel. Because streams are unbounded, aggregates are computed over windows: tumbling windows divide time into fixed, non-overlapping blocks (each minute), while sliding windows overlap (the last 5 minutes, updated every minute). Stream systems must also be fault tolerant, recovering from machine failures without losing or double-counting events. Popular platforms include Apache Kafka (messaging), Apache Storm, Apache Flink, Spark Structured Streaming, Apache Samza, Amazon Kinesis and IBM Streams.
| Basis | Batch processing | Stream processing |
|---|---|---|
| Data | Bounded, stored | Unbounded, in motion |
| Latency | Minutes to hours | Milliseconds to seconds |
| Example | Monthly payroll, daily reports | Fraud alerts, live dashboards |
Worked example – tumbling windows and parallel throughput.
- Clicks arrive at seconds 5, 20, 50, 65, 70 and 130. With 1-minute tumbling windows, window [0, 60) contains 3 clicks, [60, 120) contains 2 and [120, 180) contains 1, so the operator emits the counts 3, 2, 1.
- One counting operator can handle 25,000 events per second. If the stream carries 90,000 events per second, the system needs ⌈90,000 / 25,000⌉ = 4 parallel instances, giving a capacity of 100,000 events per second with 10% headroom.
7.4 Sampling data in a stream
Because the whole stream cannot be stored, a common strategy is to keep a representative sample and answer queries from it. The difficulty is to make the sample representative for the question being asked.
Fixed-proportion sampling. To keep about 1 element in 10, each element's key is hashed into 10 buckets and the element is kept only if it lands in bucket 0. Hashing (rather than a random coin toss for each element) ensures that the same key is always treated the same way. The key must match the question. If the question is about users' behaviour — for example "what fraction of a user's search queries are repeats?" — we must hash on the user ID and keep all queries of 1 in 10 users. Sampling 1 in 10 individual queries breaks up each user's history and gives a badly wrong answer, as the example shows.
Worked example 1 – sampling the wrong key. A user issues s = 80 queries once and d = 10 queries twice, so 90 distinct queries of which 10 are repeated. True fraction of repeated queries = 10 / 90 = 11.1%.
- If 1 in 10 queries is sampled, a once-issued query appears in the sample with probability 1/10, so expected 80 / 10 = 8 appear.
- A repeated query appears twice only if both copies are chosen: probability (1/10)² = 1/100, so expected 10 / 100 = 0.1 appear twice.
- It appears exactly once with probability 2 × (1/10) × (9/10) = 18/100, so expected 10 × 18 / 100 = 1.8 appear once.
- Estimated repeat fraction = 0.1 / (8 + 1.8 + 0.1) = 0.1 / 9.9 = 1.0% — eleven times too low.
- Sampling on user ID keeps all 100 queries of each chosen user, so the estimate is the correct 11.1%.
Reservoir sampling keeps a fixed-size sample of s elements from a stream of unknown length so that, at every moment, each element seen so far has the same chance of being in the sample. Store the first s elements; when the n-th element arrives (n > s), keep it with probability s / n, and if it is kept, it replaces a randomly chosen element of the reservoir.
Worked example 2 – reservoir of size s = 2. The stream is a, b, c, d.
- a and b fill the reservoir: {a, b}.
- c arrives (n = 3): kept with probability 2/3. P(a survives this step) = 1 − (2/3)(1/2) = 2/3, and likewise for b, so each of a, b, c is in the reservoir with probability 2/3 = s/n.
- d arrives (n = 4): kept with probability 2/4 = 1/2. Each earlier element survives with probability 1 − (1/2)(1/2) = 3/4, so its overall probability is (2/3) × (3/4) = 1/2, and d's probability is also 1/2 = s/n. Every element is equally likely, as required.
7.5 Filtering streams – Bloom filter
Filtering passes through only the stream elements that satisfy a condition, for example e-mails whose sender belongs to a list of one billion approved addresses. Checking membership exactly would require storing the whole list, which may not fit in memory. A Bloom filter solves this approximately using a bit array B of n bits, all initially 0, and k independent hash functions h₁ … hₖ. To add a key x, set the bits B[h₁(x)], …, B[hₖ(x)] to 1. To test a key y, check the bits B[h₁(y)], …, B[hₖ(y)]: if any of them is 0, y was definitely not added; if all are 1, y was probably added. A Bloom filter never gives a false negative, but it can give a false positive when other keys happen to have set all of y's bits. With m keys inserted, the false-positive probability is approximately (1 − e^(−km/n))^k, and it is smallest when k ≈ (n/m) ln 2.
Worked example 1 – inserting and testing keys. n = 10 bits, h₁(x) = x mod 10 and h₂(x) = (2x + 3) mod 10.
- Insert 15: h₁ = 5, h₂ = 33 mod 10 = 3 → set bits 5 and 3.
- Insert 23: h₁ = 3, h₂ = 49 mod 10 = 9 → set bits 3 and 9. The array now has bits 3, 5, 9 set.
- Test 17: h₁ = 7 → bit 7 is 0, so 17 is definitely not in the set.
- Test 25: h₁ = 5, h₂ = 53 mod 10 = 3 → bits 5 and 3 are both 1, so the filter says "probably yes" — but 25 was never inserted. This is a false positive.
Worked example 2 – choosing k. A filter has n = 8 billion bits for m = 1 billion approved addresses, so n/m = 8.
- k = 1: false-positive rate = 1 − e^(−1/8) = 1 − 0.8825 = 11.75%.
- k = 2: (1 − e^(−2/8))² = (1 − 0.7788)² = 0.2212² = 4.89%.
- Optimal k ≈ 8 × ln 2 = 8 × 0.693 = 5.5, so try k = 6: (1 − e^(−6/8))⁶ = (1 − 0.4724)⁶ = 0.5276⁶ = 2.16%.
- With 1 GB of memory (8 billion bits), the filter blocks about 98% of unwanted e-mails and never blocks an approved sender.
Read more on the blog: Bloom Filtering.
Independent study notes written in my own words, for learning purposes. Not affiliated with any university or course provider. R, RStudio, Hadoop, Amazon S3, Tableau, Power BI and other product names are trademarks of their respective owners.