College 8: DataStreams

Question 1

Characteristics of datastreams

Answer 1

• Incomplete Data: Not all data is available at once.
• High-Speed: Data arrives very quickly.
• Limited Storage: The system can only store a small part of the stream.
• Huge Volume: Continuous, possibly infinite data.
• One-Pass Algorithms: Can only scan data once.
• Non-Stationary Distribution: Requires fast, real-time processing.

Question 2

Handling data streams

Answer 2

• Online learning
• Sampling
• Windowing functions

Question 3

Online learning

Answer 3

Continuously update model with new data.
- Small updates: make small updates as new data arrives.
- Initial training: use initial data to train the model.
- Concept drift: model adapts to new patterns over time

Question 4

Sampling datastreams

Answer 4

• Fixed proportion sampling: store a fixed ratio of the data
• Random sampling: maintain a random sample of fixed size
• Reservoir sampling: store first s elements, for each new element, replace an old one with a certain probability

Question 5

Windowing models

Answer 5

• Sliding window: keep only most recent data items
• Tumbling window: process data in non-overlapping batches
• Hopping window: process overlapping data chunks
• Exponentially decaying window: give more weight to recent data

Question 6

Querying datastreams

Answer 6

• Filtering: select elements with specific properties
• Counting distinct elements: count unique elements in the stream
• Estimating moments: calculate statistics like average and std
• Finding frequent elements: identify popular items

Question 7

Filtering datastreams

Answer 7

• Bloom filters: efficiently test membership of elements in a set using a bit array. All set to 0 and using k independent hash functions
• Counting distinct elements: use approximate methods like the Flajolet-Martin algorithm