Advanced SearchTechniques for Large Scale Data Analytics
Pavel Zezula and Jan Sedmidubsky
Masaryk University
http://disa.fi.muni.cz
 Similarity search examples:
 Images, faces, motions, time series…
 + visual examples
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 2
 Many problems can be expressed as
finding “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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 3
Given: High dimensional data points 𝒙 𝟏, 𝒙 𝟐, …
 For example: Image is a long vector of pixel colors
1 2 1
0 2 1
0 1 0
→ [1 2 1 0 2 1 0 1 0]
 And some distance function 𝒅(𝒙 𝟏, 𝒙 𝟐)
 Which quantifies the “distance” between 𝒙 𝟏 and 𝒙 𝟐
 𝒙𝒊, 𝒙𝒋) that are
within some distance threshold 𝒅 𝒙𝒊, 𝒙𝒋 ≤ 𝒔
 Note: Naïve solution would take 𝑶 𝑵 𝟐

where 𝑵 is the number of data points
 MAGIC: This can be done in 𝑶 𝑵 !! How?
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 4
! How?
! How?
𝒙 𝒊 𝒙𝒙 𝒙 𝒊 𝒊𝒊 𝒙 𝒊 , 𝒙 𝒋 𝒙𝒙 𝒙 𝒋 𝒋𝒋 𝒙 𝒋 ) that are within some distance
threshold 𝒅𝒅 𝒙 𝒊 , 𝒙 𝒋 𝒙 𝒊 𝒙𝒙 𝒙 𝒊 𝒊𝒊 𝒙 𝒊 , 𝒙 𝒋 𝒙𝒙 𝒙 𝒋 𝒋𝒋 𝒙 𝒋 𝒙 𝒊 , 𝒙 𝒋 ≤𝒔𝒔
Given: High dimensional data points 𝒙 𝟏, 𝒙 𝟐, …
 For example: Image is a long vector of pixel colors
1 2 1
0 2 1
0 1 0
→ [1 2 1 0 2 1 0 1 0]
 And some distance function 𝒅(𝒙 𝟏, 𝒙 𝟐)
 Which quantifies the “distance” between 𝒙 𝟏 and 𝒙 𝟐
 MAGIC: This can be done in 𝑶 𝑵 ! !! How?
 MAGIC: This can be done in 𝑶 𝑵 ! !! How?
where 𝑵 is the number of data points
 MAGIC: This can be done in 𝑶 𝑵 !! How?
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 4
 Goal: Find near-neighbors in high-dim. space
 We formally define “near neighbors” as
points that are a “small distance” apart
 For each application, we first need to define
what “distance” means
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 6
 Goal: Find near-neighbors in high-dim. space
 We formally define “near neighbors” as
points 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 their
intersection divided by the size of their union:
sim(C1, C2) = |C1C2|/|C1C2|
 Jaccard distance: d(C1, C2) = 1 - |C1C2|/|C1C2|
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
3 in intersection
8 in union
Jaccard similarity= 3/8
Jaccard distance = 5/8
6
 Goal: Given a large number (𝑵 in the millions or
billions) of documents, find “near duplicate” pairs
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 7
 Goal: Given a large number (𝑵 in the millions or
billions) 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”
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 7
 Goal: Given a large number (𝑵 in the millions or
billions) 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 7
1. Shingling: Convert documents to sets
2. Min-Hashing: Convert large sets to short
signatures, while preserving similarity
3. Locality-Sensitive Hashing: Focus on
pairs of signatures likely to be from
similar documents
 Candidate pairs!
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 8
Docu-
ment
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 9
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 9
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
Signatures:
short integer
vectors that
represent the
sets, and
reflect their
similarity
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 9
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
Signatures:
short integer
vectors that
represent the
sets, and
reflect their
similarity
Locality-
Sensitive
Hashing
Candidate
pairs:
those pairs
of signatures
that we need
to test for
similarity
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 9
Step 1: Shingling: Convert documents to sets
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
 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!
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 11
 A k-shingle (or k-gram) for a document is a
sequence of k tokens that appears in the doc
 Tokens can be characters, words or something
else, 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}
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 12
 To compress long shingles, we can hash them
to (say) 4 bytes
 Represent a document by the set of hash
values of its k-shingles
 Idea: Two documents could (rarely) appear to have
shingles 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}
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 13
 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|
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 14
 Documents that have lots of shingles in
common have similar text, even if the text
appears in different order
 Caveat: You must pick k large enough, or most
documents will have most shingles
 k = 5 is OK for short documents
 k = 10 is better for long documents
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 15
 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…
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 16
Step 2: Minhashing: Convert large sets to
short signatures, while preserving similarity
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
Signatures:
short integer
vectors that
represent the
sets, and
reflect their
similarity
 Many similarity problems can be
formalized as finding subsets that
have significant intersection
 Encode sets using 0/1 (bit, boolean) vectors
 One dimension per element in the universal set
 Interpret set intersection as bitwise AND, and
set 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 18
 Rows = elements (shingles)
 Columns = sets (documents)
 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!
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 19
 Rows = elements (shingles)
 Columns = sets (documents)
 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!
 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/6Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0101
0111
1001
1000
1010
1011
0111
Documents
Shingles
19
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 20
 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)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 21
 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” of
signatures h(C1) and h(C2)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 22
 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” of
signatures 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” pairs
of near duplicate docs hash into the same bucket!
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 22
 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 suitable
hash function
 There is a suitable hash function for
the Jaccard similarity: It is called Min-Hashing
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 23
 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 in
which column C has value 1:
h (C) = min (C)
 Use several (e.g., 100) independent hash
functions (that is, permutations) to create a
signature of a column
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 24
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
4
5
1
6
7
3
2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
Signature matrix M
1212
4
5
1
6
7
3
2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
Signature matrix M
1212
4
5
1
6
7
3
2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
2nd element of the permutation
is the first to map to a 1
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
Signature matrix M
1212
5
7
6
3
1
2
4
1412
4
5
1
6
7
3
2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
2nd element of the permutation
is the first to map to a 1
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
Signature matrix M
1212
5
7
6
3
1
2
4
1412
4
5
1
6
7
3
2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
2nd element of the permutation
is the first to map to a 1
4th element of the permutation
is the first to map to a 1
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
3
4
7
2
6
1
5
Signature matrix M
1212
5
7
6
3
1
2
4
1412
4
5
1
6
7
3
2
2121
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
2nd element of the permutation
is the first to map to a 1
4th element of the permutation
is the first to map to a 1
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
25
3
4
7
2
6
1
5
Signature matrix M
1212
5
7
6
3
1
2
4
1412
4
5
1
6
7
3
2
2121
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
2nd element of the permutation
is the first to map to a 1
4th element of the permutation
is the first to map to a 1
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)Permutation 
Note: Another (equivalent) way is to
store row indexes: 1 5 1 5
2 3 1 3
6 4 6 4
25
 Choose a random permutation 
 Claim: Pr[h(C1) = h(C2)] = sim(C1, C2)
 Why?
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
01
10
00
11
00
00
One of the two
cols had to have
1 at position y
26
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
01
10
00
11
00
00
One of the two
cols had to have
1 at position y
26
 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|
 It is equally likely that any y X is mapped to the min element
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
01
10
00
11
00
00
One of the two
cols had to have
1 at position y
26
 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|
 It is equally likely that any y X is mapped to the min element
 Let y be s.t. (y) = min((C1C2))
 Then either: (y) = min((C1)) if y  C1 , or
(y) = min((C2)) if y  C2
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
01
10
00
11
00
00
One of the two
cols had to have
1 at position y
26
 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|
 It is equally likely that any y X is mapped to the min element
 Let y be s.t. (y) = min((C1C2))
 Then either: (y) = min((C1)) if y  C1 , or
(y) = min((C2)) if y  C2
 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)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
01
10
00
11
00
00
One of the two
cols had to have
1 at position y
26
 We know: Pr[h(C1) = h(C2)] = sim(C1, C2)
 Now generalize to multiple hash functions
 The similarity of two signatures is the
fraction of the hash functions in which they
agree
 Note: Because of the Min-Hash property, the
similarity of columns is the same as the
expected similarity of their signatures
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 28
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
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
Signature matrix M
1212
5
7
6
3
1
2
4
1412
4
5
1
6
7
3
2
2121
0101
0101
1010
1010
1010
1001
0101
Input matrix (Shingles x Documents)
3
4
7
2
6
1
5
Permutation 
29
 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, the
index of the first row that has a 1 in column C
sig(C)[i] = min (i(C))
 Note: The sketch (signature) of document C is
small ~𝟏𝟎𝟎 bytes!
 We achieved our goal! We “compressed”
long bit vectors into short signatures
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 30
 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” for
the min-hash value
 Initialize all sig(C)[i] = 
 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)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
How to pick a random
hash function h(x)?
Universal hashing:
ha,b(x)=((a·x+b) mod p) mod N
where:
a,b … random integers
p … prime number (p > N)
31
Step 3: Locality-Sensitive Hashing:
Focus on pairs of signatures likely to be from
similar documents
Docu-
ment
The set
of strings
of length k
that appear
in the doc-
ument
Signatures:
short integer
vectors that
represent the
sets, and
reflect their
similarity
Locality-
Sensitive
Hashing
Candidate
pairs:
those pairs
of signatures
that we need
to test for
similarity
 Goal: Find documents with Jaccard similarity at
least s (for some similarity threshold, e.g., s=0.8)
 LSH – General idea: Use a function f(x,y) that
tells whether x and y is a candidate pair: a pair
of 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 the
same bucket is a candidate pair
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
33
 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 of
their 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
34
 Big idea: Hash columns of
signature matrix M several times
 Arrange that (only) similar columns are
likely to hash to the same bucket, with
high probability
 Candidate pairs are those that hash to
the same bucket
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
35
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
Signature matrix M
r rows
per band
b bands
One
signature
1212
1412
2121
36
 Divide matrix M into b bands of r rows
 For each band, hash its portion of each
column to a hash table with k buckets
 Make k as large as possible
 Candidate column pairs are those that hash
to the same bucket for ≥ 1 band
 Tune b and r to catch most similar pairs,
but few non-similar pairs
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 37
Matrix M
r rows b bands
Buckets
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 38
Matrix M
r rows b bands
Buckets
Columns 2 and 6
are probably identical
(candidate pair)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 38
Matrix M
r rows b bands
Buckets
Columns 2 and 6
are probably identical
(candidate pair)
Columns 6 and 7 are
surely different.
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 38
 There are enough buckets that columns are
unlikely to hash to the same bucket unless
they 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 39
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 that
are at least s = 0.8 similar
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
40
 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)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
41
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
41
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
41
 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)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
42
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
42
 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 their
similarity is below threshold s
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
42
 Pick:
 The number of Min-Hashes (rows of M)
 The number of bands b, and
 The number of rows r per band
to 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
1212
1412
2121
43
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
Similaritythresholds
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 44
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
Similaritythresholds
No chance
if t < s
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 44
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
Similaritythresholds
No chance
if t < s
Probability = 1
if t > s
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 44
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
45
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
45
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
Remember:
Probability of
equal hash-values
= similarity
Similarity t =sim(C1, C2) of two sets
Probability
of sharing
a bucket
45
 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 46
t r
All rows
of a band
are equal
1 Some
row
of a band
unequal
( )b
No bands
identical
1 At
least
one band
identical
s ~ (1/b)1/r
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
Similarity t=sim(C1, C2) of two sets
Probability
of sharing
a bucket
47
 Similarity threshold s
 Prob. that at least 1 band is identical:
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
s 1-(1-sr)b
.2 .006
.3 .047
.4 .186
.5 .470
.6 .802
.7 .975
.8 .9996
48
 Picking r and b to get the best S-curve
 50 hash-functions (r=5, b=10)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Blue area: False Negative rate
Green area: False Positive rate
Similarity
Prob.sharingabucket
49
 Picking r and b to get the best S-curve
 50 hash-functions (r=5, b=10)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Blue area: False Negative rate
Green area: False Positive rate
Similarity
Prob.sharingabucket
49
 Picking r and b to get the best S-curve
 50 hash-functions (r=5, b=10)
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212)
0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 0.9 1
0
0.1
0.2
0.3
0.4
0.5
0.6
0.7
0.8
0.9
1
Blue area: False Negative rate
Green area: False Positive rate
Similarity
Prob.sharingabucket
49
 Tune M, b, r to get almost all pairs with
similar signatures, but eliminate most pairs
that 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
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 50
 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 generate
signatures 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 of
signatures likely to be from similar documents
 We used hashing to find candidate pairs of similarity  s
Pavel Zezula, Jan Sedmidubsky. Advanced Search Techniques for Large Scale Data Analytics (PA212) 51