3. Data Streams

Question 1

What are the 2 forms of queries for a data stream system?

Answer 1

1. Ad-hoc queries: Normal queries asking one time about streams
2. Standing queries: Queries that are asked about the stream at all times

Question 2

What is the stream model?

Answer 2

A model of processing data where input elements enter at a rapid rate at one or more input ports

Question 3

What types of problems can be solved using data streams?

Answer 3

1. Queries over sliding windows
2. Filtering data streams
3. Estimating moments

Question 4

What is the sliding window?

Answer 4

An approach for answering data stream queries which ask about a window of the N most recent elements received

Question 5

What is the issue that can occur with sliding window in terms of data size?

Answer 5

1. N may be too large to fit in memory or even on disk
2. N could fit in disk but there are so many streams that windows for all cannot be stored

Question 6

What is the issue with attempting to count the number of 1’s in a sliding window and how can we resolve it?

Answer 6

The issue is that we cannot afford to store N bits. We resolve this by using methods that provide us an approximate answer

Question 7

What is the uniformity assumption for counting 1’s?

Answer 7

Assumes that 1’s and 0’s are distributed uniformly across the window so we can use earlier results to estimate

Question 8

What is the equation when using the uniformity assumption for counting 1’s?

Answer 8

N * (S/(S+Z)) where S is the number of 1s from the beginning of the stream and Z is the number of zeros from the beginning of the stream

Question 9

What is the DGIM method?

Answer 9

A method for counting 1’s that does not assume uniformity. It is never off by more than 50%

Question 10

What is a DGIM bucket?

Answer 10

A record consisting of the timestamp of its end and the number of 1s between its beginning and its end. The DGIM method breaks the window into buckets where each bucket holds a number of 1s which is a power of 2

Question 11

How can we represent a stream using DGIM buckets?

Answer 11

Start at the most recent elements. Create 1 or 2 buckets with the same power-of-2 number of 1s. The buckets do not overlap and buckets get increasingly bigger as we move to the left to less recent elements. Buckets disappear when their end-time is more than N time units in the past

Question 12

How do we update DGIM buckets when a new bit arrives to the window?

Answer 12

1. If it is 0 do nothing
2. If it is 1, add it to the smallest bucket. If the bucket becomes too big or there are too many buckets of a certain size then combine buckets upwards until they are resorted

Question 13

How can we estimate the number of 1’s in the most recent N bits using DGIM?

Answer 13

1. Sum the sizes of all buckets but the last that does not fit in the window
2. Add half the size of the last bucket

Question 14

How can we estimate the number of 1’s in the most recent k bits where k < N?

Answer 14

1. Find the earliest bucket B that overlaps with k
2. Sum the sizes of all buckets earlier than B
3. Add half the size of B

Question 15

What is the goal of filtering data streams?

Answer 15

Determining which tuples of the stream are in a given list of keys S

Question 16

Why can a hash table not be used to filter a data stream?

Answer 16

We do not have enough memory to store the entire list of keys we are looking for as we could be processing millions of filters on the same stream

Question 17

What is a bloom filter?

Answer 17

A technique for filtering data streams made up of an array of bits with a number of hash functions

Question 18

How is a bloom filter used to detect if elements have been seen before?

Answer 18

1. All bits are initially set to 0
2. When an input arrives, we set to 1 the bits h(x) for each hash function h
3. If all of the bit positions are already 1 we say we have seen y before

Question 19

What is the issue with a bloom filter?

Answer 19

It can give false positives as hash collisions can occur

Question 20

What is the probability of a false positive in a bloom filter?

Answer 20

Depends on density of 1’s and the number of hash functions
=(fraction of 1’s)^# of hash functions

Question 21

What is the goal of estimating moments of a data stream?

Answer 21

Estimating summary statistics like average and standard deviation of the last k elements

Question 22

What is the formula for the kth moment?

Answer 22

Sum of all (mi)^k for all i in A where A is a set of N values and mi is the number of times i occurs in the stream

Question 23

What are the special case moments?

Answer 23

1. 0th moment which is the number of distinct elements
2. 1st moment which is the length of the stream
3. 2nd moment (surprise moment) which is a measure of how uneven the distribution is

Question 24

What is AMS?

Answer 24

A method for estimating moments of a stream

Question 25

What is the formula for the second moment for a particular variable X of the stream?

Answer 25

f(X) = n(2c-1) where n is the length of the stream and c is the count of element i stored in X.val

Question 26

How do we estimate the second moment using AMS when keeping track of multiple variables?

Answer 26

Take the average of f(X) = n(2c-1) for all X that we are tracking

Question 27

What is the issue with the AMS method for estimating the second moment?

Answer 27

We assumed there was a length of the stream n but real streams go on forever