3.4. LOCALITY-SENSITIVE HASHING FOR DOCUMENTS
95
s
1 −(1 −sr)b
.2
.006
.3
.047
.4
.186
.5
.470
.6
.802
.7
.975
.8
.9996
Figure 3.9: Values of the S-curve for b = 20 and r = 5
chances to become a candidate. Only roughly one in 3000 pairs that are as high
as 80% similar will fail to become a candidate pair and thus be a false negative.
✷
3.4.3
Combining the Techniques
We can now give an approach to ﬁnding the set of candidate pairs for similar
documents and then discovering the truly similar documents among them. It
must be emphasized that this approach can produce false negatives – pairs of
similar documents that are not identiﬁed as such because they never become
a candidate pair. There will also be false positives – candidate pairs that are
evaluated, but are found not to be suﬃciently similar.
1. Pick a value of k and construct from each document the set of k-shingles.
Optionally, hash the k-shingles to shorter bucket numbers.
2. Sort the document-shingle pairs to order them by shingle.
3. Pick a length n for the minhash signatures.
Feed the sorted list to the
algorithm of Section 3.3.5 to compute the minhash signatures for all the
documents.
4. Choose a threshold t that deﬁnes how similar documents have to be in
order for them to be regarded as a desired “similar pair.” Pick a number
of bands b and a number of rows r such that br = n, and the threshold
t is approximately (1/b)1/r. If avoidance of false negatives is important,
you may wish to select b and r to produce a threshold lower than t; if
speed is important and you wish to limit false positives, select b and r to
produce a higher threshold.
5. Construct candidate pairs by applying the LSH technique of Section 3.4.1.
6. Examine each candidate pair’s signatures and determine whether the frac-
tion of components in which they agree is at least t.
