Naïve Sampling Scenario: Restaurant Orders

Goal

A restaurant wants to measure:

“How many customers order the same dish twice?”

Step 1 — Real Data (Ground Truth)

Suppose customers ordered:

Alice: Pizza, Salad, Pasta → all different (unique)
Bob: Burger, Burger → duplicate
Sara: Sushi, Sushi → duplicate

Summary

• Unique orders:
Pizza, Salad, Pasta → x = 3

• Duplicate orders:
Burger (twice), Sushi (twice) → d = 2

Correct Answer

Distinct dishes:
Pizza, Salad, Pasta, Burger, Sushi → 5 total

Duplicate dishes = 2

True fraction:
2 / 5 = 40%

Step 2 — Naïve Sampling (10%)

pg. 1
Now the restaurant says:

“Let’s randomly keep only 10% of all orders”

What might happen?

Sample outcome:

Order Kept?

Pizza

Salad

Pasta

Burger (1st)

Burger (2nd)

Sushi (1st)

Sushi (2nd)

Sample becomes:
Burger

What went wrong?

Originally:
Burger, Burger → duplicate

After sampling:
Burger → looks like a single order

The duplicate is broken

Another possible sample

pg. 2
Sushi

Again:

• Sushi was duplicate

• Now looks unique

What the restaurant concludes

They look at sampled data and say:

“Almost no one orders the same dish twice”

But reality was:

40% of dishes were duplicates

Why this happens

Because:

Orders are sampled individually, not as groups

The core issue

Duplicates come in pairs:

Burger, Burger

But sampling treats them like:

Burger → maybe kept
Burger → maybe dropped

Most pairs get:

• broken

• or disappear

pg. 3
 Super Simple Analogy

You want to study:

How many people wear pairs of shoes

But you randomly collect individual shoes

Result:

• Many pairs → become single shoes

• You conclude:
“People mostly wear one shoe”

Obviously wrong

What should be done instead?

Instead of sampling orders:

Sample customers

Example:

• Pick 10% of customers

• Keep all their orders

Now:

Bob → Burger, Burger (still duplicate )

Sara → Sushi, Sushi (still duplicate )

Relationships are preserved

Final takeaway

Naïve sampling breaks relationships → and once relationships are broken, your conclusions
become wrong.

pg. 4
 Real-World Example: Food Delivery App

Goal

A company like Uber Eats wants to analyze:

“How often do users reorder the same food?”

Step 1 — What the data looks like

Each event (stream element) is:

(user, order, time)

Example:
(Alice, Burger, 12:00)
(Alice, Burger, 12:10)
(Bob, Pizza, 12:05)
(Bob, Sushi, 12:20)
(Charlie, Pizza, 12:30)
(Charlie, Pizza, 12:40)

Problem with naïve sampling

If we randomly sample orders:

Keep:
(Alice, Burger)
(Bob, Pizza)
(Charlie, Pizza)

What happened?

• Alice’s duplicate Burger → broken

• Charlie’s duplicate Pizza → broken

Now everything looks like single orders

pg. 1
 Key-Based Sampling Idea

Instead of sampling orders:

Sample users

Step-by-Step (from your notes)

Step 1: Choose a key

key = user

Step 2: Hash the key

Assign each user to a bucket:

Alice → bucket 1
Bob → bucket 7
Charlie → bucket 0

Step 3: Keep some buckets

We want 30% of users

So:
b = 10 buckets
a = 3 → keep buckets 0,1,2

Step 4: Apply rule

Keep users in:

bucket 0,1,2

So we keep:
Alice (bucket 1)
Charlie (bucket 0)

pg. 2
We drop:
Bob (bucket 7)

Final Sample
(Alice, Burger)
(Alice, Burger)
(Charlie, Pizza)
(Charlie, Pizza)

What’s the benefit?

All relationships are preserved:

• Alice’s duplicate → still duplicate

• Charlie’s duplicate → still duplicate

Key Insight

We selected 30% of users, not 30% of orders

Why this works

Because:

All data for the same user is either:

• ALL kept

• OR ALL removed

Simple Analogy

Instead of:

• Sampling individual photos

pg. 3
 You sample entire albums

So:

• You don’t lose context

• You don’t break relationships

When to use this

Use key-based sampling when data has structure:

• User sessions

• Transactions per customer

• Messages per user

• Clicks per session

One-line takeaway

Key-based sampling keeps related data together — so your analysis stays correct.

pg. 4
S = [] # reservoir of size s. this is your sample container. It will always hold exactly s elements

# Step 1: take the first s elements, put them directly into the sample
for i in range(s):
[Link](stream[i])

# Step 2
for n in range(s, N):
r = [Link](0, n)
if r < s:
S[r] = stream[n]

Big Picture First

We want:

Keep exactly s items, but make sure every item in the stream has an equal chance to be in
the final sample.

The Code
S = [] # reservoir of size s

This is your sample container

It will always hold exactly s elements

Step 1 — Fill the reservoir

for i in range(s):
[Link](stream[i])

What this means:

• Take the first s elements

• Put them directly into the sample

Example (s = 3)

pg. 1
Stream:
A, B, C, D, E, F...

After Step 1:
S = [A, B, C]

Why we do this

At the beginning:

• We don’t have enough data yet

• So, we just fill the reservoir

Step 2 — Process the rest of the stream

for n in range(s, N):

Now we process elements one by one:

• n = s → next element
• n = s+1, s+2, ...

Key Line (Most Important!)

r = [Link](0, n)

Pick a random number between 0 and n

What this really does

It simulates:

“Should this new element be included?”

Decision Step
if r < s:

pg. 2
 This means:

• Probability that r < s is:

𝑠
𝑛+1

So this line implements:

“Keep this element with probability ≈ s/n”

Replacement Step
S[r] = stream[n]

If we decide to keep it:

• Replace one random element in the reservoir

Why random replacement?

So that:

• No element is favored

• Everyone has equal chance

Full Walkthrough Example

Example: s = 2

Stream:
A, B, C, D

Step 1:
S = [A, B]

pg. 3
Step 2: Process C (n = 2)
r = [Link](0, 2)

Possible values:
0, 1, 2

Case 1: r = 2
r < 2 → False

Do nothing
S = [A, B]

Case 2: r = 0 or 1

Replace:
S = [C, B] or S = [A, C]

Step 3: Process D (n = 3)
r = [Link](0, 3)

Values:
0, 1, 2, 3

• If r < 2 → replace

• Else → ignore

Why this works (simple intuition)

New elements:

• Have a chance to enter:

pg. 4
s / n

Old elements:

• Might get replaced

• But only fairly (randomly)

So:

Nobody is guaranteed to stay

Nobody is unfairly removed

Balance

• New items → chance to enter

• Old items → chance to stay

Perfect fairness

Key Insight (Important!)

Older elements gradually get replaced, but not unfairly

Common Confusion

“Why not just randomly pick s items at the end?”

Because:

• You don’t store the full stream

• You only see each element once

“Why random index r?”

pg. 5
Because:

• It controls probability AND

• decides which element to replace

pg. 6
 Filtering Example

Email Spam Filtering (Trusted Senders)

Goal

An email system wants to quickly decide:

“Is this email from a trusted sender?”

Step 1 — Known Set 𝑺

The system has a list of trusted emails:

alice@[Link]
bob@[Link]
carol@[Link]

This is set S

Problem

• The list could contain millions of emails

• Storing and checking all of them directly is expensive

Solution: Bit Array + Hashing

Step 2 — Create Bit Array

We create a bit array:

B = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] (size n = 10)

Step 3 — Hash Each Trusted Email

Use a hash function:

pg. 1
h(email) → index from 0 to 9

Example mapping:

Email h(email) Action

alice@[Link] 2 B[2] = 1

bob@[Link] 7 B[7] = 1

carol@[Link] 4 B[4] = 1

Bit array becomes:

B = [0, 0, 1, 0, 1, 0, 0, 1, 0, 0]

Step 4 — Incoming Emails (Stream)

Now emails arrive one by one:

Example 1: Trusted sender

incoming: alice@[Link]
h = 2
B[2] = 1 → ACCEPT

Example 2: Unknown sender

incoming: hacker@[Link]
h = 3
B[3] = 0 → REJECT

Example 3: False positive (important!)

incoming: random@[Link]
h = 4
B[4] = 1 → ACCEPT

pg. 2
 But:

• random@[Link] is NOT in S

Why did this happen?

Because:

Different emails can hash to the same index

carol@[Link] → h = 4
random@[Link] → h = 4

Collision → causes false positive

Summary in This Scenario

If email is trusted
It WILL always pass

✔ No false negatives

If email is NOT trusted

It MIGHT pass

False positive possible

Intuition

Think of the bit array as:

A quick “maybe yes / definitely no” filter

Meaning of results:

pg. 3
 Result Meaning

𝑩[𝒉(𝒂)] = 𝟎 Definitely NOT in set

B[h(a)] = 1 Maybe in set

Simple Analogy

Imagine:

• A building has a list of authorized people

• Instead of storing names, you store fingerprint codes in boxes

When someone arrives:

• You check a box

• If empty → definitely not allowed

• If full → maybe allowed (could be collision)

When this is useful

• Fast filtering before expensive checks

• Large-scale systems:

o Spam filtering

o Network packet filtering

o Database query optimization

Key Trade-off

Benefit Cost

Very fast Some false positives

Very small memory Not perfectly accurate

pg. 4
pg. 5
 Example for False Positives
Event Wristbands

Scenario

At a large music festival:

• There are n = 100 lockers (think of these as the bit array slots)

• Each attendee gets assigned lockers using a hash-like system

• We don’t store names — only mark lockers as “used”

Step 1 — The Setup

• Lockers = bit array 𝐵

B = [0, 0, 0, ..., 0] (100 lockers)

• Each person (element) is assigned a locker randomly:

h(person) → locker index

Step 2 — People Arrive (Throwing Darts)

Each new person:

• Randomly hits a locker (like throwing a dart )

• Marks it as used:
B[h(person)] = 1

Example

Suppose 30 people arrive:

• Some lockers get hit once

• Some get hit multiple times

pg. 1
 • Some remain empty

Key Question

What is the probability that a locker is used (i.e., bit = 1)?

Interpretation of the Formula

Result:

1 𝑚
1 − (1− 𝑛)

means:

Probability a locker has been hit at least once

Approximation:

1 − 𝑒 −𝑚/𝑛

easier to reason about

Concrete Numbers

Case 1: Few people (low load)

• 𝑛 = 100lockers

• 𝑚 = 10people

1 − 𝑒 −10/100 = 1 − 𝑒 −0.1 ≈ 0.095

Only ~9.5% of lockers are used

pg. 2
 Meaning

• Most lockers are empty

• Very low chance of confusion

• False positives are rare

Case 2: More people

• 𝑚 = 100

1 − 𝑒 −1 ≈ 0.63

~63% of lockers are used

Meaning

• Many lockers are filled

• Chance of collision increases

Case 3: Too many people

• 𝑚 = 300

1 − 𝑒 −3 ≈ 0.95

95% of lockers are used

Now the Problem (False Positives)

Imagine checking a person:

You ask:

pg. 3
“Is this person registered?”

System checks:
B[h(person)]

Case:

• Locker is marked (1)

You say: “Yes, registered”

BUT:

• That locker might have been marked by someone else

False positive

What goes wrong when many bits are 1

When lockers are almost all filled:

B = [1, 1, 1, 1, 1, 1, 1, ...]

Now:

• Every check returns:

"Yes"

Even for people who never registered

Critical Insight

More elements → more buckets filled → more collisions → more false positives

Intuition Summary

“Throwing darts” means:

pg. 4
 • Each element randomly occupies space

• Over time → space fills up

As filling increases:

% buckets filled False positives

Low Rare

Medium Noticeable

High Very frequent

~100% Everything passes

Simple Analogy

Imagine:

• You check if a seat is reserved

• But you only know if someone sat there before

If most seats have been used:

You assume:
"Every seat is reserved"

Obviously wrong

Final Takeaway

A bit array works well only when it is sparse (many zeros)

Once it fills up → it loses its ability to filter

pg. 5
 Filtering Data Streams & Bloom Filters

1. Problem Setting: Filtering Data Streams

1.1 Core Problem

We are given:

• A data stream of tuples

• A set of keys 𝑆

Objective

Determine whether each incoming stream element belongs to the set 𝑆

Formal View

• Each element is a tuple (e.g., (user, query, time))

• We want to check:

𝑎∈𝑆?

1.2 Naïve Solution

Use a hash table:

• Store all elements of 𝑆

• For each incoming element:

o Lookup in 𝑂(1)

Problem

Memory is insufficient

pg. 1
 Real-World Constraint

• ∣ 𝑆 ∣ can be extremely large

• Example:

o Millions or billions of keys

o Multiple filters applied simultaneously

Tip

We need:

A compact representation of set 𝑆

2. Applications

Example 1: Email Spam Filtering

• Known set 𝑆: trusted email addresses

• If sender ∈ 𝑆→ NOT spam

Example 2: Publish-Subscribe Systems

• Users subscribe to keywords

• Incoming messages must be matched against:

o Many keyword sets

Key Challenge

• Fast membership testing

• Low memory usage

pg. 2
3. First-Cut Solution: Bit Array + Hashing

3.1 Idea

Instead of storing elements directly:

Store their hash signatures in a bit array

3.2 Data Structure

• Bit array 𝐵of size 𝑛

• Initially:
B = [0, 0, 0, ..., 0]

3.3 Algorithm (Initialization Phase)

Step 1: Choose Hash Function

ℎ: 𝑆 → [0, 𝑛 − 1]

Step 2: Insert Elements

For each 𝑠 ∈ 𝑆:

𝐵[ℎ(𝑠)] = 1

3.4 Query Phase (Streaming)

For each incoming element 𝑎:

1. Compute:

ℎ(𝑎)

pg. 3
 2. Check:

• If 𝐵[ℎ(𝑎)] = 1→ output

• Else → discard

Example

See “4. Example Bit Array and [Link]”

Bit array:

0010010101000

If:

h(a) = 5 → B[5] = 1 → KEEP

h(a) = 3 → B[3] = 0 → DROP

4. Behavior of First-Cut Solution

Guarantee

• If 𝑎 ∈ 𝑆→ it will always pass

No false negatives

Issue

• Some 𝑎 ∉ 𝑆 may still pass

False positives

Summary

Case Result
𝑎 ∈ 𝑆 Always accepted
𝑎 ∉ 𝑆 Sometimes accepted

pg. 4
 Important Property

This method has:

• False positives

• No false negatives

5. Quantifying False Positives (Intuition)

See “5. Example - False [Link]”

5.1 “Throwing Darts” Model

Analogy

• 𝑛 buckets = bit array

• 𝑚 elements = darts

• Each element hashes randomly

Question

What is the probability a bucket is hit at least once?

5.2 Result

Probability that a bit is set to 1:

1 𝑚
1 − (1− 𝑛)

Approximation (for large 𝒏):

1 − 𝑒 −𝑚/𝑛

pg. 5
 Interpretation

• More elements → more bits set

• More bits set → higher false positive rate

Pitfall

If too many bits become 1:

• Filter becomes useless (everything passes)

6. Bloom Filter (Improved Solution)

6.1 Key Idea

Use multiple hash functions instead of one

Parameters

• 𝑚 = ∣ 𝑆 ∣ (number of elements)

• 𝑛 = ∣ 𝐵 ∣ (size of bit array)

• 𝑘 = number of hash functions

6.2 Initialization

Step-by-Step

1. Initialize bit array:

B = [0, 0, ..., 0]

2. For each element 𝑠 ∈ 𝑆:

For each hash function 𝒉𝒊 , 𝒊 = 𝟏, . . . , 𝒌:

pg. 6
 B[h_i(s)] = 1

6.3 Query Phase

For incoming element 𝑥:

1. Compute all hashes:

ℎ1 (𝑥), ℎ2 (𝑥), . . . , ℎ𝑘 (𝑥)

2. Check all bits:

• If ALL are 1 → output (possibly in 𝑆)

• Else → discard

Key Logic

Only accept if ALL hash checks pass

Summary

Condition Result

All bits = 1 Possibly in S

Any bit = 0 Definitely NOT in S

Important Property

• False positives

• No false negatives

7. Bloom Filter Analysis

pg. 7
7.1 Fraction of Bits Set to 1

We set bits using 𝑘 ⋅ 𝑚 hash operations:

Fraction of 1s = 1 − 𝑒 −𝑘𝑚/𝑛

7.2 False Positive Probability

𝑘
(1−𝑒 −𝑘𝑚/𝑛 )

Interpretation

• Increasing 𝑘:

o Initially reduces error

o Eventually increases error

8. Choosing Optimal Number of Hash Functions

Formula
𝑛
𝑘= ln 2
𝑚

Example

• 𝑚 = 1 billion

• 𝑛 = 8 billion

𝑘 = 8ln 2 ≈ 5.54 ≈ 6

pg. 8
Resulting Error

≈ 2.35%

Tip

Always choose:

𝑘 ≈ (𝑛/𝑚)ln 2

9. Practical Insights

Tip: When to Use Bloom Filters

• Pre-filtering large datasets

• Database query optimization

• Network packet filtering

• Caching systems

Pitfall: Too Many Hash Functions

• Increased computation

• Higher collision correlation

Pitfall: Too Small Bit Array

• High false positive rate

10. Implementation Considerations

10.1 One Large Bit Array vs Multiple Small Arrays

pg. 9
Result

Equivalent mathematically

But:

• One large array → simpler implementation

10.2 Parallelization

• Hash functions can be computed independently

• Efficient for hardware / distributed systems

11. Final Summary

Key Concepts

• Hash-based filtering saves memory

• Bloom filters improve accuracy

• Trade-off:

o Memory vs false positives

Guarantees

• No false negatives

• Efficient membership testing

Final Insight

Bloom filters are probabilistic data structures —

they trade perfect accuracy for massive scalability

pg. 10
Data Streams