Great — you’ve pasted Section 4.2: Sampling Data in a Stream from Mining of Massive Datasets (2019).
Let me explain it step by step in detail, with examples and intuition so it’s easy to follow.
---
4.2 Sampling Data in a Stream – Explained
🔹 Motivation
Data streams are huge — you cannot store everything.
Instead, we want a sample that is:
1. Representative of the whole stream.
2. Usable for many different queries (not just one fixed query).
Example:
A search engine gets a stream of queries → (user, query, time).
We want to ask: “What fraction of a user’s queries were repeats in the past month?”
But we can only afford to store 1/10th of the stream.
---
4.2.1 A Motivating Example
Naive idea: Sample each query independently with probability 1/10.
For each arriving query → flip a random number (0–9).
Keep it only if the number = 0.
👉 Problem: This distorts results.
Why?
Suppose a user issues:
s queries that appear only once.
d queries that appear twice.
In the 1/10 sample:
Queries issued once: expected s/10 appear.
Queries issued twice:
Both copies appear with prob = 1/100 → expected d/100.
Only one copy appears with prob = 18/100 → expected 18d/100.
So in the sample:
Twice-appearing queries are underrepresented.
The computed fraction of repeated queries is wrong:
True fraction = d / (s + d).
Sample fraction = d / (10s + 19d).
Conclusion:
Sampling queries independently ruins relationships between duplicates.
---
4.2.2 Obtaining a Representative Sample
👉 Correct approach:
Instead of sampling queries, sample users.
Method:
1. Choose 1/10 of the users.
2. Keep all queries from those users.
How to implement:
Maintain a list of users with “in” or “out” decision.
When a new user appears:
Flip a random number (0–9).
If 0 → mark as “in” (keep all their queries).
Else → mark as “out.”
But storing all users can be expensive.
Trick using hashing:
Hash user name → number between 0–9.
If result = 0 → include user.
Else → exclude.
✅ Advantage:
No need to store user list.
Same user always hashes to the same bucket → consistent sampling.
Hash acts like a deterministic random number generator.
Generalization:
To sample fraction a/b: hash user into b buckets.
Keep if hash value < a.
---
4.2.3 The General Sampling Problem
Streams usually consist of tuples with multiple components.
Example: (user, query, time) → 3 components.
We must decide which component(s) act as the key.
Possible choices:
Key = user → sample users.
Key = query → sample queries.
Key = (user, query) pair → sample user–query combinations.
Rule:
To sample fraction a/b:
Hash the key into b buckets.
Accept if hash value < a.
This ensures we sample entire groups of related tuples, not random fragments.
---
4.2.4 Varying the Sample Size
Problem: As the stream grows, the sample gets bigger (since we keep all tuples for sampled keys).
But memory is limited.
Solution: Use a hash threshold:
1. Pick a large range for the hash function (say 0 … B–1).
2. Maintain a threshold t.
3. Rule: keep all tuples where h(key) ≤ t.
As more data arrives:
If sample size exceeds memory → reduce threshold t.
This discards some keys (and all their tuples).
Efficiency tips:
Instead of lowering t by 1, drop multiple buckets at once.
Keep an index on hash values to quickly remove all tuples with those values.
---
✅ Summary
Naive query sampling distorts statistics.
Better approach: sample by key (e.g., user) and include all related tuples.
Implementation: use hashing instead of storing user lists.
General problem: choose key fields carefully depending on analysis.
Dynamic sampling: adjust hash threshold as memory fills up.
---
💡 Key Insight:
In stream sampling, always sample keys (groups), not individual tuples, to preserve meaningful
relationships in the data.
---
Would you like me to also draw a diagram/flowchart (e.g., how hashing decides inclusion) so it’s easier
to visualize this sampling process?
Perfect 👍 Let’s explain Sampling Data in a Stream with a real-time example so it feels practical.
---
🚗 Real-Time Example: Ride-Hailing App (like Uber/Ola)
Imagine we run a ride-hailing platform that processes a huge stream of data every second:
Stream tuples:
(driver_id, rider_id, trip_time, fare, location)
We want to analyze rider behavior but can’t store all trips (too big!).
Suppose we can only afford to keep 10% of the data.
---
1 Naive Approach: Sample Each Trip
1️⃣
For every trip, generate a random number (0–9).
Keep the trip only if the number = 0.
👉 Problem:
Suppose one rider takes 20 trips in a month, 5 of them repeated from the same location.
Random trip sampling may keep only 1 or 2 of their trips → losing the repetition pattern.
Analysis like “How many riders repeat trips from the same location?” becomes inaccurate, because
duplicates may disappear in the sample.
This is exactly like the search query example in the book → repeated patterns are miscounted.
---
2️⃣Better Approach: Sample Riders (the key)
Instead of sampling each trip, we sample riders.
Pick 10% of the riders, and keep all trips from those riders.
How to do it:
Use rider_id as the key.
Hash rider_id into 10 buckets.
If the hash value = 0 → keep this rider → store all their trips.
If not → discard all trips from this rider.
👉 Advantage:
If rider X makes repeated trips, we preserve that repetition in the sample.
Queries like “What fraction of trips are repeats?” remain accurate because we are seeing complete rider
histories (just for fewer riders).
---
3️⃣Generalization
We can choose different keys depending on what we want to study:
Key = rider_id → sample riders (study rider behavior).
Key = driver_id → sample drivers (study driver patterns).
Key = (rider_id, driver_id) → study specific rider–driver relationships.
---
4️⃣Varying Sample Size
Over time, trips keep coming in. If we always keep all trips for sampled riders:
Memory will eventually overflow.
👉 Solution:
Use a larger hash space (say 0…99,999).
Keep only keys with hash(key) ≤ t.
If sample is too big, lower t.
Example: if t = 10,000 → keep 10% of riders.
If sample grows too much, reduce t to 5,000 → now keep only 5% of riders.
This way, the sample stays within budget.
---
✅ Real-World Takeaway
In streaming systems (search engines, ride-hailing, e-commerce, sensors), sampling entire users/items
(via hashing keys) gives representative and consistent samples.
If you only sample individual events (queries, trips, clicks), you lose relationships like duplicates, repeat
behaviors, or correlations.
---
👉 Would you like me to also create a diagram (flowchart) showing:
how a tuple enters,
gets hashed on the key (say rider_id),
and is either accepted or rejected into the sample?
Perfect 👍 You’ve shared the Filtering Streams (Bloom Filtering) section from Mining of Massive Datasets
(Leskovec, Rajaraman, Ullman, 2019). Let me now explain this in an elaborate but clear way with real-
time examples, just like I did for Sampling Streams.
---
📘 Filtering Streams (Detailed Explanation)
---
1. What is Filtering in Streams?
Filtering (or selection) = choosing only those tuples (records) in a stream that meet some condition.
If the condition is simple and computable (e.g., first component < 10), filtering is easy.
Problem: What if the condition requires membership in a very large set that cannot fit in main memory?
Example:
We want to accept only emails from a set S of 1 billion trusted addresses.
Stream = (email_address, email_content).
But storing S in RAM is impossible (too big).
A disk lookup for every email would be too slow.
We need a memory-efficient structure to quickly filter most spam without full lookups.
---
2. Bloom Filtering – The Idea
A Bloom Filter is a space-efficient probabilistic data structure for set membership tests.
It can tell:
Definitely Not in Set ✅
Possibly in Set (false positives possible) ⚠️
It never gives false negatives.
---
Motivating Example
Available memory = 1 GB → = 8 billion bits.
Allowed addresses = 1 billion.
Step 1: Hash each allowed email → set that bit = 1.
Step 2: For an incoming email:
If hash points to 0 → reject (definitely spam).
If hash points to 1 → accept (might be spam).
Result:
About 7/8 of spam is eliminated immediately.
Remaining 1/8 (false positives) can be checked against disk if needed.
Multiple filters (cascade) can reduce false positives further.
---
3. Structure of a Bloom Filter
A Bloom Filter consists of:
1. Bit Array of length n (initially all 0).
2. k Hash Functions (h1, h2, …, hk) → map a key to positions in bit array.
3. Set S of size m (keys to be stored).
---
Initialization
For each key K in S:
Compute h1(K), h2(K), …, hk(K)
Set all those bit positions = 1.
---
Testing a Key
For a new key K:
Compute h1(K), h2(K), …, hk(K).
If any bit = 0 → K is definitely not in S.
If all bits = 1 → K is probably in S (may be false positive).
---
4. False Positives in Bloom Filters
A false positive happens when a key not in S happens to have all its hash positions set by other
elements.
Probability of false positive depends on:
n = bit array size
m = number of items in set
k = number of hash functions
General trade-offs:
Larger n → fewer collisions → fewer false positives.
More hash functions → reduces false positives initially, but too many makes bits overcrowded.
---
5. Real-Time Examples
1. Email Spam Filtering
Store trusted addresses in Bloom filter.
Incoming email → check filter before disk lookup.
Saves huge computation by rejecting most spam quickly.
2. Web Browser Cache
A browser may use a Bloom filter to check if a URL is cached.
If Bloom filter says "no" → skip disk lookup.
If "maybe" → check disk.
3. Databases / Big Data Systems
Hadoop and Spark use Bloom filters to avoid unnecessary data fetches.
Example: filtering which rows/partitions might contain matching data.
4. Networking
Routers use Bloom filters to detect if a packet’s destination is in a set of blocked/allowed addresses.
---
✅ Summary
Filtering = selecting stream elements that meet a condition.
Challenge: membership test with huge sets.
Bloom Filter: memory-efficient, probabilistic solution.
Uses bit array + multiple hash functions.
No false negatives, only false positives.
Greatly reduces number of expensive lookups.
Real-time uses: spam filtering, cache checking, databases, and networks.
---
on?
Got it 👍 Let me give you detailed real-time examples of Filtering Streams using Bloom Filters, so it
connects to daily-life or industry use cases.
---
🌍 Real-Time Examples of Bloom Filtering in Streams
---
1. Email Spam Filtering (Classic Example)
Suppose Gmail or Outlook receives millions of emails every second.
It maintains a huge set S of trusted email addresses (say, 1 billion).
When a new email arrives:
The system hashes the sender’s address into a Bloom filter.
If the bit = 0 → the sender is definitely not trusted (spam → reject immediately).
If the bit = 1 → the sender might be trusted → do a deeper disk/database check.
👉 Result: The filter instantly removes ~87% of spam without heavy computation.
---
2. Netflix / Amazon – Movie Recommendation Filtering
Netflix has a set of licensed movies/shows available in a user’s region.
When a user searches for a title in the stream of queries:
Bloom filter checks if the movie ID exists in the "licensed set."
If not in filter → show "Not available in your region" instantly.
If maybe in filter → fetch full details from the catalog database.
👉 Benefit: Saves huge database lookups on every query.
---
3. Web Browser Cache Lookup
Your browser stores recently visited sites in a cache.
Bloom filter keeps track of cached URLs.
When you type a URL:
If Bloom filter says "not cached" → browser skips disk and fetches from the web.
If "maybe cached" → browser checks local storage.
👉 Benefit: Avoids unnecessary disk I/O, speeds up browsing.
---
4. Big Data Systems (Hadoop / Spark)
In Hadoop/Spark jobs, data is split across many servers (partitions).
Suppose you run a query: “find users who purchased product X.”
Bloom filter is built for each partition to mark which products exist.
Before scanning full data:
System checks Bloom filter of each partition.
If Bloom filter = "no match" → skip that partition.
If "maybe" → scan further.
👉 Benefit: Saves hours of computation by skipping irrelevant partitions.
---
5. Network Security (Firewall / Router Filtering)
Firewalls often maintain a set of blocked IP addresses.
Incoming packet → hash its source IP into a Bloom filter.
If not in filter → forward the packet.
If maybe in filter → check against full blacklist.
👉 Benefit: Can block millions of malicious IPs in real time using small memory.
---
✅ Summary of Real-Time Uses
Email spam filters → block unwanted senders fast.
Streaming platforms (Netflix, Amazon) → quick availability checks.
Web browsers → fast cache lookup.
Big Data (Hadoop, Spark) → avoid scanning useless data.
Networking → firewall and routing optimization.
---
Would you like me to also prepare these examples as exam-style answers (5-mark / 10-mark) so you can
directly use them in tests?