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

High dim.
data

Graph
data

Infinite
data

Machinelearning

Apps

Locality
sensitive
hashing

PageRank,
SimRank

Filteringdata
streams

SVM

Recommender systems

Clustering

Network
AnalysisWebadvertising

Decision
Trees

Association
Rules

Dimensional
ity
reduction

Spam
Detection

Queries on
streams

Perceptron,kNN

Duplicate
document
detection

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

2

[Hays and Efros, SIGGRAPH 2007]

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

3

[Hays and Efros, SIGGRAPH 2007]

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

4

[Hays and Efros, SIGGRAPH 2007]

10 nearest neighbors from a collection of 20,000 images
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

5

[Hays and Efros, SIGGRAPH 2007]

10 nearest neighbors from a collection of 2 million images
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

6 Many problems can be expressed asfinding “similar” sets:
 Find near-neighbors in high-dimensional space Examples: Pages with similar words
 For duplicate detection, classification by topic

 Customers who purchased similar products
 Products with similar customer sets

 Images with similar features
 Users who visited similar websites

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

7 Given: High dimensional data points  ,  , …

 For example: Image is a long vector of pixel colors
1 2 1
0 2 1 → 121021010
0 1 0

 And some distance function ,  

 Which quantifies the “distance” between  and  Goal: Find all pairs of data points  ,   that arewithin some distance threshold  ,    Note: Naïve solution would take   
where  is the number of data points
 MAGIC: This can be done in   !! How?
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

8 Last time: Finding frequent pairs
Items 1 KCount of pair {i,j}in the dataNaïve solution:
Single pass but requires
space quadratic in thenumber of items
NK

number of distinct items
number of items with support ≥ s

Items 1 K

Items 1 N

Items 1 N

Count of pair {i,j}in the data

A-Priori:First pass: Find frequent singletons
For a pair to be a frequent paircandidate, its singletons have to be
frequent!
Second pass:Count only candidate pairs!

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

9 Last time: Finding frequent pairs Further improvement: PCY

 Pass 1:

Items 1 N

 Count exact frequency of each item: Take pairs of items {i,j}, hash them into B buckets andcount of the number of pairs that hashed to each bucket:
2

Buckets 1 B
1Basket 1: {1,2,3}
Pairs: {1,2} {1,3} {2,3}

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

10 Last time: Finding frequent pairs Further improvement: PCY

 Pass 1:

Items 1 N

 Count exact frequency of each item: Take pairs of items {i,j}, hash them into B buckets andcount of the number of pairs that hashed to each bucket:

 Pass 2:
 For a pair {i,j} to be a candidate fora frequent pair, its singletons {i}, {j}have to be frequent and the pairhas to hash to a frequent bucket!

3

Buckets 1 B
1
2

Basket 1: {1,2,3}
Pairs: {1,2} {1,3} {2,3}Basket 2: {1,2,4}
Pairs: {1,2} {1,4} {2,4}

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

11 Last time: Finding frequent pairs Further
improvement:
PCY
Previous
lecture: A-Priori
Main Pass1:idea: Candidates

Items 1 N
Instead of keeping a count of each pair, only keep a count Count
exactpairs!
frequency of each item:of candidate

 Takepairs lecture:of items {i,j},
hash
them
B buckets
Today’sFind
pairs
ofintosimilardocsandcountof theCandidates
number of pairs that hashed to each bucket:
Main idea:-- Pass 1: Take documents and hash them to buckets suchthat1 B
Buckets
 Pass2:
documents that are similar hash to the same bucket
3

1

2

 For
a pair{i,j}compare
to be adocuments
candidatethat
forare candidates-- Pass
2: Only
they hasheda samebucket)havea(i.e.,
frequent
pair,toits
singletons
Basket 1: {1,2,3}2
Benefits:
Insteadandof O(N
comparisons,O(N)Pairs:{1,2} {1,3} {2,3}tobe frequentits ) has
to hash we needcomparisons to find similar documents
Basket 2: {1,2,4}
to a frequent bucket!

Pairs: {1,2} {1,4} {2,4}

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

12 Goal: Find near-neighbors in high-dim. space We formally define “near neighbors” aspoints that are a “small distance” apart For each application, we first need to define

what “distance” means
 Today: Jaccard distance/similarity
 The Jaccard similarity of two sets is the size of theirintersection divided by the size of their union:sim(C1, C2) = |C1∩C2|/|C1∪C2|
 Jaccard distance: d(C1, C2) = 1 - |C1∩C2|/|C1∪C2|
3 in intersection
8 in union
Jaccard similarity= 3/8
Jaccard distance = 5/8
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

14 Goal: Given a large number ( in the millions orbillions) of documents, find “near duplicate” pairs
 Applications: Mirror websites, or approximate mirrors
 Don’t want to show both in search results

 Similar news articles at many news sites
 Cluster articles by “same story”

 Problems: Many small pieces of one document can appear
out of order in another Too many documents to compare all pairs Documents are so large or so many that they cannot
fit in main memory
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

15

1.

Shingling: Convert documents to sets

2.

Min-Hashing: Convert large sets to short
signatures, while preserving similarity

3.

Locality-Sensitive Hashing: Focus onpairs of signatures likely to be fromsimilar documentsCandidate pairs!

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

16

LocalitySensitive
HashingDocument

The setof stringsof length kthat appear
in the document

Signatures:short integer
vectors that
represent thesets, andreflect theirsimilarity

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

Candidatepairs:
those pairsof signaturesthat we needto test forsimilarity

17Document

The setof stringsof length kthat appear
in the document

Step 1: Shingling: Convert documents to sets Step 1: Shingling: Convert documents to sets
 Simple approaches: Document = set of words appearing in document Document = set of “important” words
 Don’t work well for this application. Why?
 Need to account for ordering of words!
 A different way: Shingles!

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

19 A k-shingle (or k-gram) for a document is asequence of k tokens that appears in the doc
 Tokens can be characters, words or somethingelse, depending on the application
 Assume tokens = characters for examples
 Example: k=2; document D1 = abcab

Set of 2-shingles: S(D1) = {ab, bc, ca} Option: Shingles as a bag (multiset), count ab
twice: S’(D1) = {ab, bc, ca, ab}
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

20 To compress long shingles, we can hash themto (say) 4 bytes
 Represent a document by the set of hashvalues of its k-shingles
 Idea: Two documents could (rarely) appear to haveshingles in common, when in fact only the hashvalues were shared Example: k=2; document D1= abcab

Set of 2-shingles: S(D1) = {ab, bc, ca}
Hash the singles: h(D1) = {1, 5, 7}
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

21 Document D1 is a set of its k-shingles C1=S(D1) Equivalently, each document is a

0/1 vector in the space of k-shingles
 Each unique shingle is a dimension
 Vectors are very sparse A natural similarity measure is the

Jaccard similarity:sim(D1, D2) = |C1∩C2|/|C1∪C2|

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

22 Documents that have lots of shingles incommon have similar text, even if the text
appears in different order Caveat: You must pick k large enough, or mostdocuments will have most shingles
 k = 5 is OK for short documents k = 10 is better for long documents

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

23 Suppose we need to find near-duplicate

documents among    million documents Naïvely, we would have to compute pairwise

Jaccard similarities for every pair of docs
   / ≈ 5*1011 comparisons At 105 secs/day and 106 comparisons/sec,
it would take 5 days
 For    million, it takes more than a year…
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

24Document

The setof stringsof length kthat appear
in the document

Signatures:short integer
vectors that
represent thesets, andreflect theirsimilarity

Step 2: Minhashing: Convert large sets toshort signatures, while preserving similarity

 Many similarity problems can beformalized as finding subsets thathave significant intersection
 Encode sets using 0/1 (bit, boolean) vectors
 One dimension per element in the universal set
 Interpret set intersection as bitwise AND, andset union as bitwise OR Example: C1 = 10111; C2 = 10011

 Size of intersection = 3; size of union = 4,
 Jaccard similarity (not distance) = 3/4
 Distance: d(C1,C2) = 1 – (Jaccard similarity) = 1/4
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

26 Rows = elements (shingles) Columns = sets (documents)

 Each document is a column:
 Example: sim(C1 ,C2) = ?
 Size of intersection = 3; size of union = 6,
Jaccard similarity (not distance) = 3/6
 d(C1,C2) = 1 – (Jaccard similarity) = 3/6

Shingles 1 in row e and column s if and only
if e is a member of s Column similarity is the Jaccard
similarity of the corresponding
sets (rows with value 1)
 Typical matrix is sparse!

Documents

1

1

1

0

1
0

1
1

0
0

1
1

0

0

0

1

1

0

0

1

1

1

1

0

1

0

1

0

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

27 So far:

 Documents → Sets of shingles
 Represent sets as boolean vectors in a matrix
 Next goal: Find similar columns while

computing small signatures
 Similarity of columns == similarity of signatures

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

28 Next Goal: Find similar columns, Small signatures Naïve approach: 1) Signatures of columns: small summaries of columns 2) Examine pairs of signatures to find similar columns
 Essential: Similarities of signatures and columns are related 3) Optional: Check that columns with similar signatures
are really similar Warnings:

 Comparing all pairs may take too much time: Job for LSH
 These methods can produce false negatives, and even false
positives (if the optional check is not made)J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

29 Key idea: “hash” each column C to a small

signature h(C), such that: (1) h(C) is small enough that the signature fits in RAM
 (2) sim(C1, C2) is the same as the “similarity” ofsignatures h(C1) and h(C2) Goal: Find a hash function h(·) such that: If sim(C1,C2) is high, then with high prob. h(C1) = h(C2) If sim(C1,C2) is low, then with high prob. h(C1) ≠ h(C2) Hash docs into buckets. Expect that “most” pairsof near duplicate docs hash into the same bucket!
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

30 Goal: Find a hash function h(·) such that: if sim(C1,C2) is high, then with high prob. h(C1) = h(C2) if sim(C1,C2) is low, then with high prob. h(C1) ≠ h(C2) Clearly, the hash function depends on

the similarity metric:
 Not all similarity metrics have a suitablehash function
 There is a suitable hash function for

the Jaccard similarity: It is called Min-Hashing
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

31 Imagine the rows of the boolean matrix

permuted under random permutation π Define a “hash” function hπ(C) = the index of

the first (in the permuted order π) row inwhich column C has value 1:
hπ (C) = minπ π(C) Use several (e.g., 100) independent hashfunctions (that is, permutations) to create asignature of a column
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

32Note: Another (equivalent) way is tostore row indexes: 1
5 1 5

2
6

3
4

1
6

3
4

2nd element of the permutationis the first to map to a 1

Permutation π

Input matrix (Shingles x Documents)

2 4 3

1

0

1

0

2

1

2

1

3

2 4

1

0

0

1

2

1

4

1

7

1 7

0

1

0

1

1

2

1

2

6 3 2

0

1

0

1

1

6 6

0

1

0

1

5

7 1

1

0

1

0

4 5 5

1

0

1

0

Signature matrix M

4th element of the permutationis the first to map to a 1

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

33 Choose a random permutation π Claim: Pr[hπ(C1) = hπ(C2)] = sim(C1, C2)
 Why?

 Let X be a doc (set of shingles), y∈ X is a shingle
 Then: Pr[ππ(y) = min(ππ(X))] = 1/|X|

0

0

0

0

1

1

0

0

0

1

1

0

 It is equally likely that any y∈ X is mapped to the min element

 Let y be s.t. π(y) = min(π(C1∪C2))
One of the two Then either: π(y) = min(π(C1)) if y ∈ C1 , orcols had to haveπ(y) = min(π(C2)) if y ∈ C2
1 at position y So the prob. that both are true is the prob. y ∈ C1 ∩ C2
 Pr[min(ππ(C1))=min(ππ(C2))]=|C1∩C2|/|C1∪C2|= sim(C1, C2)
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

34 Given cols C1 and C2, rows may be classified as:

C1
C2
A
1
1
B
1
0
C
0
1
D
0
0
 a = # rows of type A, etc.
 Note: sim(C1, C2) = a/(a +b +c)
 Then: Pr[h(C1) = h(C2)] = Sim(C1, C2)

 Look down the cols C1 and C2 until we see a 1
 If it’s a type-A row, then h(C1) = h(C2)
If a type-B or type-C row, then not
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

35 We know: Pr[hπ(C1) = hπ(C2)] = sim(C1, C2)
 Now generalize to multiple hash functions
 The similarity of two signatures is thefraction of the hash functions in which theyagree Note: Because of the Min-Hash property, thesimilarity of columns is the same as the
expected similarity of their signatures
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

36Permutation π

Input matrix (Shingles x Documents)

2 4 3

1

0

1

0

2

1

2

1

3

2 4

1

0

0

1

2

1

4

1

7

1 7

0

1

0

1

1

2

1

2

6 3 2

0

1

0

1

1

6 6

0

1

0

1

5

7 1

1

0

1

0

4 5 5

1

0

1

0

Signature matrix M

Similarities:
1-3 2-4 1-2 3-4
Col/Col 0.75 0.75 0 0
Sig/Sig 0.67 1.00 0 0

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

37 Pick K=100 random permutations of the rows
 Think of sig(C) as a column vector
 sig(C)[i] = according to the i-th permutation, theindex of the first row that has a 1 in column C
sig(C)[i] = min (ππi(C))
 Note: The sketch (signature) of document C issmall ~ bytes!
 We achieved our goal! We “compressed”

long bit vectors into short signatures
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

38 Permuting rows even once is prohibitive Row hashing!

 Pick K = 100 hash functions ki
 Ordering under ki gives a random row permutation!
 One-pass implementation

 For each column C and hash-func. ki keep a “slot” forthe min-hash value
 Initialize all sig(C)[i] = ∞How to pick a randomhash function h(x)?
 Scan rows looking for 1s
 Suppose row j has 1 in column C
 Then for each ki :
 If ki(j) < sig(C)[i], then sig(C)[i] ← ki(j)Universal hashing:ha,b(x)=((a·x+b) mod p) mod N
where:
a,b
random integerspprime number (p > N)

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

39

LocalitySensitive
HashingDocument

The setof stringsof length kthat appear
in the document

Signatures:short integer
vectors that
represent thesets, andreflect theirsimilarity

Candidatepairs:
those pairsof signaturesthat we needto test forsimilarity

Step 3: Locality-Sensitive Hashing:
Focus on pairs of signatures likely to be fromsimilar documents

2

1

4

1

1

2

1

2

2

1

2

1

 Goal: Find documents with Jaccard similarity atleast s (for some similarity threshold, e.g., s=0.8)
 LSH – General idea: Use a function f(x,y) thattells whether x and y is a candidate pair: a pairof elements whose similarity must be evaluated For Min-Hash matrices: Hash columns of signature matrix M to many buckets
 Each pair of documents that hashes into thesame bucket is a candidate pair
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

41

2

1

4

1

1

2

1

2

2

1

2

1

 Pick a similarity threshold s (0 < s < 1)
 Columns x and y of M are a candidate pair if

their signatures agree on at least fraction s oftheir rows:
M (i, x) = M (i, y) for at least frac. s values of i
 We expect documents x and y to have the same
(Jaccard) similarity as their signatures

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

42

2

1

4

1

1

2

1

2

2

1

2

1

 Big idea: Hash columns ofsignature matrix M several times
 Arrange that (only) similar columns arelikely to hash to the same bucket, withhigh probability
 Candidate pairs are those that hash to

the same bucket

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

43

2

1

4

1

1

2

1

2

2

1

2

1

r rowsper bandb bandsOne
signature

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

44 Divide matrix M into b bands of r rows
 For each band, hash its portion of eachcolumn to a hash table with k buckets
 Make k as large as possible
 Candidate column pairs are those that hashto the same bucket for ≥ 1 band Tune b and r to catch most similar pairs,

but few non-similar pairs
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

45

Buckets

Columns 2 and 6
are probably identical(candidate pair)
Columns 6 and 7 aresurely different.

Matrix M

r rowsb bands

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

46 There are enough buckets that columns areunlikely to hash to the same bucket unlessthey are identical in a particular band
 Hereafter, we assume that “same bucket”

means “identical in that band”
 Assumption needed only to simplify analysis,

not for correctness of algorithm

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

47

2

1

4

1

1

2

1

2

2

1

2

1

Assume the following case: Suppose 100,000 columns of M (100k docs)
 Signatures of 100 integers (rows)
 Therefore, signatures take 40Mb
 Choose b = 20 bands of r = 5 integers/band Goal: Find pairs of documents thatare at least s = 0.8 similar

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

48

2

1

4

1

1

2

1

2

2

1

2

1

 Find pairs of ≥ s=0.8 similarity, set b=20, r=5
 Assume: sim(C1, C2) = 0.8

 Since sim(C1, C2) ≥ s, we want C1, C2 to be a candidate
pair: We want them to hash to at least 1 common bucket(at least one band is identical)
 Probability C1, C2 identical in one particular

band: (0.8)5 = 0.328
 Probability C1, C2 are not similar in all of the 20
bands: (1-0.328)20 = 0.00035
 i.e., about 1/3000th of the 80%-similar column pairs
are false negatives (we miss them) We would find 99.965% pairs of truly similar documents
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

49

2

1

4

1

1

2

1

2

2

1

2

1

 Find pairs of ≥ s=0.8 similarity, set b=20, r=5
 Assume: sim(C1, C2) = 0.3

 Since sim(C1, C2) < s we want C1, C2 to hash to NO
common buckets (all bands should be different) Probability C1, C2 identical in one particular

band: (0.3)5 = 0.00243
 Probability C1, C2 identical in at least 1 of 20
bands: 1 - (1 - 0.00243)20 = 0.0474

 In other words, approximately 4.74% pairs of docs
with similarity 0.3% end up becoming candidate pairs
 They are false positives since we will have to examine them
(they are candidate pairs) but then it will turn out theirsimilarity is below threshold s
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

50

2

1

4

1

1

2

1

2

2

1

2

1

 Pick: The number of Min-Hashes (rows of M)
 The number of bands b, and The number of rows r per bandto balance false positives/negatives
 Example: If we had only 15 bands of 5

rows, the number of false positives would
go down, but the number of false negatives
would go up
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

51

No chance
if t < sSimilarity threshold s

Probabilityof sharing
a bucket

Probability = 1
if t > s

Similarity t =sim(C1, C2) of two sets

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

52

Probabilityof sharing
a bucket

Remember:
Probability ofequal hash-values= similarity

Similarity t =sim(C1, C2) of two sets

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

53 Columns C1 and C2 have similarity t Pick any band (r rows)

 Prob. that all rows in band equal = tr
 Prob. that some row in band unequal = 1 - tr Prob. that no band identical = (1 - tr)b
 Prob. that at least 1 band identical =1 - (1 - tr)b

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

54

At least
one bandidentical

Probabilityof sharing
a bucket

1 - (1 -t r )bs ~ (1/b)1/r

Similarity t=sim(C1, C2) of two sets

No bands
identical

Some rowof a band
unequalJ. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

All rows
of a bandare equal55 Similarity threshold s
 Prob. that at least 1 band is identical:

s
.2
.3
.4
.5
.6
.7
.8

1-(1-sr)b
.006
.047
.186
.470
.802
.975
.9996

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

56 Picking r and b to get the best S-curve 50 hash-functions (r=5, b=10)
1Prob. sharing a bucket

0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2

Blue area: False Negative rate
Green area: False Positive rate

0.1
0
0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

Similarity

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

57 Tune M, b, r to get almost all pairs withsimilar signatures, but eliminate most pairsthat do not have similar signatures
 Check in main memory that candidate pairs

really do have similar signatures Optional: In another pass through data,

check that the remaining candidate pairs
really represent similar documents

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

58 Shingling: Convert documents to sets

 We used hashing to assign each shingle an ID
 Min-Hashing: Convert large sets to short

signatures, while preserving similarity
 We used similarity preserving hashing to generatesignatures with property Pr[hπ(C1) = hπ(C2)] = sim(C1, C2)
 We used hashing to get around generating random
permutations
 Locality-Sensitive Hashing: Focus on pairs ofsignatures likely to be from similar documents
 We used hashing to find candidate pairs of similarity ≥ s
J. Leskovec, A. Rajaraman, J. Ullman: Mining of Massive Datasets, http://www.mmds.org

59