Data Streams & Streaming Algorithms

C is correct — streams like network traffic or sensor readings are potentially unbounded and have no fixed end. E is correct — distributions shift over time (concept drift); e.g. shopping patterns change by season. A is wrong — streams can be infinite by definition. B is wrong — the rate is externally imposed and uncontrolled; the system must cope with whatever rate arrives. D is wrong — streams can carry text, images, events, or any data type.

Stream elements are individual, atomic, real-time data items. B is correct — a single page-visit event is one discrete item arriving in a continuous click-stream. E is correct — a live sensor reading is a real-time atomic element arriving continuously. A is wrong — a full customer database is a static, batched dataset, not a stream element. C is wrong — a compiled monthly report is aggregated/historical data, the opposite of real-time stream elements. D is wrong — an archived log is stored batch data, not a live stream.

C is correct — computing stream statistics (median, distinct count, frequency) with limited memory is the core algorithmic challenge of streaming. E is correct — the whole point of real-time processing is fast decisions; fraud detection, anomaly alerts, and recommendations all require low latency. A is wrong — storing the entire stream is exactly what is infeasible; streaming algorithms exist precisely to avoid this. B is wrong — controlling data values is not a streaming goal. D is wrong — batching contradicts real-time processing.

A, B, D, and E are all correct — they all involve continuous, real-time data flows requiring immediate processing. Web analytics (A) processes click-streams live; network monitoring (B) analyses packet flows in real-time; telecom fraud detection (D) flags suspicious call patterns as they happen; sensor networks (E) produce continuous environmental readings. C is wrong — archiving historical weather data is a batch storage task; data is collected and stored for later analysis, not processed as a live stream.

C is correct — streams can be infinite or extremely high-volume, making full in-memory storage impossible; this is why approximate algorithms like DGIM exist. E is correct — processing everything in real-time with only a small working memory buffer is the central challenge of streaming. A is wrong — streams commonly mix data types (events, numbers, text). B is wrong — arrival rates are often bursty and unpredictable, which is precisely what makes stream management hard. D is wrong — the challenge is that datasets are large and potentially infinite, not small.

D is correct — a DSMS operates with a small, fixed working memory; it cannot store everything, so it uses synopses and approximations. E is correct — handling high velocity and volume is the defining capability that distinguishes a DSMS from a traditional DBMS. A is wrong — batch processing is the opposite of streaming; a DSMS processes elements as they arrive, not in collected batches. B is wrong — storing the entire stream defeats the purpose; a DSMS is designed precisely for when full storage is impossible. C is wrong — a DSMS actively queries and processes data in real-time; archiving without querying describes a data lake, not a DSMS.

All four non-"none" options are standard stream query types. Sampling (A) — drawing a representative subset from an ongoing stream. Sliding windows (B) — computing results over the most recent N elements, discarding older data (the basis of DGIM). Filtering (C) — retaining only elements matching a predicate (e.g., Bloom filters). Counting distinct elements (D) — estimating the number of unique items seen so far (e.g., Flajolet-Martin). E is wrong — all of the above are genuine stream query types taught in this module.

B is correct — reservoir sampling maintains a fixed-size sample of size m regardless of how long the stream grows, which is the key algorithmic goal. C is correct — sampling is the mechanism that allows real-time processing within a tight memory budget. A is wrong — storing everything is precisely what sampling avoids. D is wrong — sampling is an approximate technique; accuracy for all queries is impossible with a sample. E is wrong — in weighted random sampling (WRS), elements have different probabilities proportional to their weights; uniform probability applies only to simple random sampling, not WRS.

The naive 1-in-10 sampling approach: for each element, generate a random integer (A) in {0…9}; store the element only if the integer equals a specific target value. This gives every element an equal 1/10 probability (B) of being kept. C is wrong in isolation — while 0 could be used as the target, the key property is equal probability; C describes just one possible implementation detail, not a characteristic. D is wrong — discarding when the integer equals 9 is the same as keeping when it doesn't equal 9, which gives 9/10 probability — this isn't sampling a fixed small proportion. E is wrong — storing all elements first defeats the memory constraint that makes streaming algorithms necessary.

B is correct — the defining property of WRS is that heavier-weighted elements are more likely to appear in the sample; probability is proportional to weight. E is correct — a clean algorithm exists: assign each element a key u^(1/w) (where u is uniform random, w is weight) and keep the m elements with the largest keys. A is wrong — equal probability is simple random sampling, not WRS; the whole point of WRS is to differentiate by weight. C is wrong — the basic finite WRS algorithm requires knowing n upfront; a separate reservoir-based variant handles infinite streams. D is wrong — in a stream, probabilities are updated dynamically as new elements arrive.

The WRS formula used in the lecture is P(eᵢ) = (wᵢ × m) / (n × n) where the denominator treats each element as having average weight equal to n (a simplification where weights range 1..n). With wᵢ = 50, m = 10, n = 100: P = (50 × 10) / (100 × 100) = 500/10000 = 0.05. This matches option D. A (50/1000) = 0.05 numerically but the formula structure is wrong. B (10/100) = 0.1, which is uniform sampling ignoring weights. C (50/100) = 0.5, ignores sample size m. E divides by just n once instead of n², giving 5 which is > 1, so it cannot be a probability.