Note to other teachers and users of these slides: We would be delighted if you found this ourmaterial useful in giving your own lectures. Feel free to use these slides verbatim, or to modify
them to fit your own needs. If you make use of a significant portion of these slides in your own
lecture, please include this message, or a link to our web site: http://www.mmds.org

Mining of Massive Datasets
Jure Leskovec, Anand Rajaraman, Jeff Ullman
Stanford University

http://www.mmds.org

 More algorithms for streams:

 (1) Filtering a data stream: Bloom filters
 Select elements with property x from stream

 (2) Counting distinct elements: Flajolet-Martin
 Number of distinct elements in the last k elementsof the stream

 (3) Estimating moments: AMS method
 Estimate std. dev. of last k elements

 (4) Counting frequent items

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

2 Each element of data stream is a tuple Given a list of keys S Determine which tuples of stream are in S
 Obvious solution: Hash table

 But suppose we do not have enough memory tostore all of S in a hash table E.g., we might be processing millions of filterson the same stream

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

4 Example: Email spam filtering We know 1 billion “good” email addresses If an email comes from one of these, it is NOT
spam
 Publish-subscribe systems

 You are collecting lots of messages (news articles) People express interest in certain sets of keywords
 Determine whether each message matches user’s
interest
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

5 Given a set of keys S that we want to filter Create a bit array B of n bits, initially all 0s
 Choose a hash function h with range [0,n) Hash each member of s∈ S to one ofn buckets, and set that bit to 1, i.e., B[h(s)]=1
 Hash each element a of the stream andoutput only those that hash to bit that was
set to 1
 Output a if B[h(a)] == 1

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

6Output the item since it may be in S.
Item hashes to a bucket that at least
one of the items in S hashed to.

Item
Hash
func h0010001011000

Bit array B

Drop the item.
It hashes to a bucket set
to 0 so it is surely not in S.

 Creates false positives but no false negatives

 If the item is in S we surely output it, if not we may
still output it
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

7 |S| = 1 billion email addresses|B|= 1GB = 8 billion bits
 If the email address is in S, then it surely

hashes to a bucket that has the big set to 1,
so it always gets through (no false negatives) Approximately 1/8 of the bits are set to 1, so

about 1/8th of the addresses not in S get
through to the output (false positives)
 Actually, less than 1/8th, because more than one
address might hash to the same bit
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

8 More accurate analysis for the number offalse positives
 Consider: If we throw m darts into n equally

likely targets, what is the probability thata target gets at least one dart?
 In our case: Targets = bits/buckets
 Darts = hash values of items
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

9 We have m darts, n targets
 What is the probability that a target gets atleast one dart?
Equals 1/e
as n →∞

Equivalentn( m / n)

1 - (1 – 1/n)
Probability sometarget X not hit
by a dart

1 – e–m/n

Probability atleast one dart
hits target X

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

10 Fraction of 1s in the array B == probability of false positive = 1 – e-m/n
 Example: 109 darts, 8∙109 targets

 Fraction of 1s in B = 1 – e-1/8 = 0.1175
 Compare with our earlier estimate: 1/8 = 0.125

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

11 Consider: |S| = m, |B| = n
 Use k independent hash functions h1 ,…, hk
 Initialization:

 Set B to all 0s
 Hash each element s∈ S using each hash function hi,(note: we have aset B[hi(s)] = 1 (for each i = 1,.., k)single array B!)

 Run-time: When a stream element with key x arrives If B[hi(x)] = 1 for all i = 1,..., k then declare that x is in S
 That is, x hashes to a bucket set to 1 for every hash function hi(x) Otherwise discard the element x
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

12 What fraction of the bit vector B are 1s?

 Throwing k∙m darts at n targets
 So fraction of 1s is (1 – e-km/n)
 But we have k independent hash functions

and we only let the element x through if all khash element x to a bucket of value 1
 So, false positive probability = (1 – e-km/n)k

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

13

0.2

 m = 1 billion, n = 8 billion

 What happens as we

keep increasing k?

0.16

False positive prob.

 k = 1: (1 – e-1/8) = 0.1175
 k = 2: (1 – e-1/4)2 = 0.0493

0.18

0.14
0.12
0.1
0.08
0.06
0.04
0.02
0

2

4

6

8

10

12

14

16

18

20

Number of hash functions, k

 “Optimal” value of k: n/m ln(2) In our case: Optimal k = 8 ln(2) = 5.54 ≈ 6
 Error at k = 6: (1 – e-1/6)2 = 0.0235
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

14 Bloom filters guarantee no false negatives,and use limited memory
 Great for pre-processing before more
expensive checks Suitable for hardware implementation

 Hash function computations can be parallelized Is it better to have 1 big B or k small Bs?

 It is the same: (1 – e-km/n)k vs. (1 – e-m/(n/k))k But keeping 1 big B is simpler
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

15 Problem: Data stream consists of a universe of elements
chosen from a set of size N
 Maintain a count of the number of distinct
elements seen so far
 Obvious approach:

Maintain the set of elements seen so far
 That is, keep a hash table of all the distinct
elements seen so far
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

17 How many different words are found among

the Web pages being crawled at a site?
 Unusually low or high numbers could indicate
artificial pages (spam?) How many different Web pages does eachcustomer request in a week?
 How many distinct products have we sold in

the last week?
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

18 Real problem: What if we do not have space

to maintain the set of elements seen so far?
 Estimate the count in an unbiased way Accept that the count may have a little error,

but limit the probability that the error is large

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

19 Pick a hash function h that maps each of the

N elements to at least log2 N bits
 For each stream element a, let r(a) be thenumber of trailing 0s in h(a)
 r(a) = position of first 1 counting from the right E.g., say h(a) = 12, then 12 is 1100 in binary, so r(a) = 2

 Record R = the maximum r(a) seen

 R = maxa r(a), over all the items a seen so far Estimated number of distinct elements = 2R
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

20 Very very rough and heuristic intuition why

Flajolet-Martin works: h(a) hashes a with equal prob. to any of N values
 Then h(a) is a sequence of log2 N bits,
where 2-r fraction of all as have a tail of r zeros About 50% of as hash to ***0
 About 25% of as hash to **00
 So, if we saw the longest tail of r=2 (i.e., item hashending *100) then we have probably seen
about 4 distinct items so far

 So, it takes to hash about 2r items before wesee one with zero-suffix of length r
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

21 Now we show why Flajolet-Martin works
 Formally, we will show that probability offinding a tail of r zeros: Goes to 1 if  ≫ 
 Goes to 0 if  ≪ 
where  is the number of distinct elements
seen so far in the stream Thus, 2R will almost always be around m!

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

22 What is the probability that a given h(a) ends

in at least r zeros is 2-r
 h(a) hashes elements uniformly at random Probability that a random number ends inat least r zeros is 2-r
 Then, the probability of NOT seeing a tailof length r among m elements:   
Prob. all end infewer than r zeros.

Prob. that given h(a) ends
in fewer than r zeros

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

23

−r m

− r 2r ( m 2− r ) Note: (1 − 2 ) = (1 − 2 )≈e− m 2− r Prob. of NOT finding a tail of length r is: If m << 2r, then prob. tends to 1
−r m
− m 2− r (1 − 2 ) ≈ e= 1 as m/2r→ 0
 So, the probability of finding a tail of length r tends to 0

 If m >> 2r, then prob. tends to 0
−r m
− m 2− r (1 − 2 ) ≈ e= 0 as m/2r → ∞ So, the probability of finding a tail of length r tends to 1

 Thus, 2R will almost always be around m!
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

24 E[2R] is actually infinite Probability halves when R → R+1, but value doubles
 Workaround involves using many hashfunctions hi and getting many samples of Ri
 How are samples Ri combined?
 Average? What if one very large value  ?
 Median? All estimates are a power of 2
 Solution:
 Partition your samples into small groups Take the median of groups
 Then take the average of the medians
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

25 Suppose a stream has elements chosenfrom a set A of N values
 Let mi be the number of times value i occurs

in the stream The kth moment is∑ (m )i∈Ak

i

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org27∑ (m )i∈Aki

 0thmoment = number of distinct elements

 The problem just considered 1st moment = count of the numbers ofelements = length of the stream
 Easy to compute 2nd moment = surprise number S =a measure of how uneven the distribution is
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

28 Stream of length 100
 11 distinct values
 Item counts: 10, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9

Surprise S = 910
 Item counts: 90, 1, 1, 1, 1, 1, 1, 1 ,1, 1, 1

Surprise S = 8,110

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

29

[Alon, Matias, and Szegedy]

 AMS method works for all moments
 Gives an unbiased estimate
 We will just concentrate on the 2nd moment S
 We pick and keep track of many variables X:

 For each variable X we store X.el and X.val
 X.el corresponds to the item i X.val corresponds to the count of item i Note this requires a count in main memory,
so number of Xs is limited Our goal is to compute∑ 

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

30 How to set X.val and X.el?

 Assume stream has length n (we relax this later) Pick some random time t (t<n) to start,
so that any time is equally likely
 Let at time t the stream have item i. We set X.el = i
 Then we maintain count c (X.val = c) of the number
of is in the stream starting from the chosen time t
 Then the estimate of the 2nd moment (∑  ) is:    – 
 Note, we will keep track of multiple Xs, (X1, X2,… Xk)
and our final estimate will be/ ∑  
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

31

Count:1

2

Stream:

a

a

ma

3
b

b

b

a

b

a



∑ 
 2nd moment is ct … number of times item at time t appears
from time t onwards (c1=ma , c2=ma-1, c3=mb) ∑     
m … total count ofi∑        ⋯  Group times
by the value
seenTime t when
the last i isseen (ct=1)

Time t when
the penultimate
i is seen (ct=2)

 

item i in the stream(we are assuming
stream has length n)Time t when
the first i isseen (ct=mi)

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

32

Count:1

2

Stream:aa

 ! "#

ma

3
b

b

b

a

b

a

$
∑, & 1  3  5  ⋯  2+,  1%

 Little side calculation: 1  3  5  ⋯  2+,  1./ ./ 0$./∑,$2-  1 2
 +, +, 1
 Then  


∑


1

 



∑  
 So, 2 34
 We have the second moment (in expectation)!
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

33 For estimating kth moment we essentially use thesame algorithm but change the estimate: For k=2 we used n (2∙c – 1)
 For k=3 we use: n (3∙c2 – 3c + 1)

(where c=X.val)

 Why?

 For k=2: Remember we had 1  3  5  ⋯  2+,  1
and we showed terms 2c-1 (for c=1,…,m) sum to m2
.
1
1
∑.
 ∑.
6$ 25  1
6$ 5  ∑6$ 5  1
 So:         +1

 For k=3: c3 - (c-1)3 = 3c2 - 3c + 1
 Generally: Estimate& 5 7  5  1 7 

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

34 In practice: Compute   –  foras many variables X as you can fit in memory
 Average them in groups Take median of averages
 Problem: Streams never end

 We assumed there was a number n,
the number of positions in the stream
 But real streams go on forever, so n isa variable – the number of inputs seen so far
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

35




(1) The variables X have n as a factor –keep n separately; just hold the count in X
(2) Suppose we can only store k counts.
We must throw some Xs out as time goes on: Objective: Each starting time t is selected withprobability k/n Solution: (fixed-size sampling!)
 Choose the first k times for k variables
 When the nth element arrives (n > k), choose it withprobability k/n If you choose it, throw one of the previously stored
variables X out, with equal probability
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

36 New Problem: Given a stream, which items

appear more than s times in the window?
 Possible solution: Think of the stream ofbaskets as one binary stream per item
 1 = item present; 0 = not present
 Use DGIM to estimate counts of 1s for all items
6

10
4
3

2
2

1
1 0
010011100010100100010110110111001010110011010
N
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

38 In principle, you could count frequent pairs

or even larger sets the same way One stream per itemset
 Drawbacks:

 Only approximate
 Number of itemsets is way too big

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

39 Exponentially decaying windows: A heuristic

for selecting likely frequent item(sets) What are “currently” most popular movies?
 Instead of computing the raw count in last N elements
 Compute a smooth aggregation over the whole stream

 If stream is a1, a2,… and we are taking the sumof the stream, take the answer at time t to be:∑ 8    
 c is a constant, presumably tiny, like 10-6 or 10-9

 When new at+1 arrives:

Multiply current sum by (1-c) and add at+1
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

40 If each ai is an “item” we can compute thecharacteristic function of each possible
item x as an Exponentially Decaying Window That is: ∑ 9 ⋅    
where δi=1 if ai=x, and 0 otherwise
 Imagine that for each item x we have a binary
stream (1 if x appears, 0 if x does not appear) New item x arrives: Multiply all counts by (1-c)
 Add +1 to count for element x

 Call this sum the “weight” of item x
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

41

...

1/c
 Important property: Sum over all weights∑     is 1/[1 – (1 – c)] = 1/c
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

42 What are “currently” most popular movies?
 Suppose we want to find movies of weight > ½

 Important property: Sum over all weights∑; 1  5 ; is 1/[1 – (1 – c)] = 1/c
 Thus: There cannot be more than 2/c movies withweight of ½ or more
 So, 2/c is a limit on the number ofmovies being counted at any time

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

43 Count (some) itemsets in an E.D.W.

 What are currently “hot” itemsets?
 Problem: Too many itemsets to keep counts ofall of them in memory When a basket B comes in: Multiply all counts by (1-c)
 For uncounted items in B, create new count Add 1 to count of any item in B and to any itemset
contained in B that is already being counted
 Drop counts < ½
 Initiate new counts (next slide)J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

44 Start a count for an itemset S ⊆ B if every

proper subset of S had a count prior to arrivalof basket B
 Intuitively: If all subsets of S are being counted
this means they are “frequent/hot” and thus S has
a potential to be “hot”
 Example:

 Start counting S={i, j} iff both i and j were counted
prior to seeing B
 Start counting S={i, j, k} iff {i, j}, {i, k}, and {j, k}were all counted prior to seeing B
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

45 Counts for single items < (2/c)∙(avg. numberof items in a basket)
 Counts for larger itemsets = ??
 But we are conservative about starting

counts of large sets
 If we counted every set we saw, one basketof 20 items would initiate 1M counts

J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

46