1
00:00:00,990 --> 00:00:05,270
Now we're ready to learn and apply
the idea of locality-sensitive hashing.

2
00:00:05,270 --> 00:00:06,520
We're going to do this first for

3
00:00:06,520 --> 00:00:10,810
the special case of minhash signatures and
later see the general LSH idea.

4
00:00:12,020 --> 00:00:14,210
First, let's remember
where we've gotten so far.

5
00:00:15,920 --> 00:00:20,170
We converted documents to sets of shingles
and then we converted the presumably large

6
00:00:20,170 --> 00:00:25,600
sets of shingles to short signatures,
consistently a vectors of integers.

7
00:00:25,600 --> 00:00:29,300
We can compare two signatures
as they make quite close to

8
00:00:29,300 --> 00:00:32,420
the Jaccard similarity of
their underlying sets.

9
00:00:32,420 --> 00:00:36,070
Since the signatures are relatively short,
we can fit many of them into main memory

10
00:00:36,070 --> 00:00:40,310
at once and thus compare many different
pairs of these signatures without having

11
00:00:40,310 --> 00:00:43,930
to spend the time needed to read
each signature from disk many times.

12
00:00:46,440 --> 00:00:49,880
The idea behind LSH is to look at
the collection of elements, that is,

13
00:00:49,880 --> 00:00:54,510
signatures in our example here,
whose similar pairs we want to find and

14
00:00:54,510 --> 00:00:58,550
without constructing all pairs of
those elements, create a short list of

15
00:00:58,550 --> 00:01:03,180
candidate pairs whose similarity
actually must be measured.

16
00:01:03,180 --> 00:01:04,750
When constructing candidate pairs,

17
00:01:04,750 --> 00:01:08,650
you look only at individual elements,
not at the pairs themselves.

18
00:01:08,650 --> 00:01:13,050
All pairs that are not candidates are
assumed not to be similar even though in

19
00:01:13,050 --> 00:01:15,848
rare cases,
there will indeed be false negative.

20
00:01:15,848 --> 00:01:19,139
That is, pairs that are similar but
never checked for similarity.

21
00:01:21,090 --> 00:01:23,110
For the cases of signature matrices,

22
00:01:23,110 --> 00:01:26,070
we perform LSH by creating some
large number of hash functions.

23
00:01:27,700 --> 00:01:31,200
These are ordinary hash functions,
not minhash functions.

24
00:01:31,200 --> 00:01:35,050
For each selected hash function,
we hash columns to buckets.

25
00:01:35,050 --> 00:01:38,130
For each bucket, we make all pairs
within that bucket a candidate pair.

26
00:01:39,530 --> 00:01:42,050
A pair becomes a candidate
pair if any one or

27
00:01:42,050 --> 00:01:46,820
more of the hash functions puts
both signatures in the same bucket.

28
00:01:46,820 --> 00:01:47,430
Okay.

29
00:01:47,430 --> 00:01:50,560
We need to tune the number of hash
functions and the number of buckets for

30
00:01:50,560 --> 00:01:55,580
each hash function so that the buckets
have relatively few signatures in them.

31
00:01:55,580 --> 00:01:58,930
That way, there are not too
many candidate pairs generated.

32
00:01:58,930 --> 00:02:03,330
But we can't use too many buckets, or
else, pairs that are truly similar

33
00:02:03,330 --> 00:02:07,010
will not wind up in the same bucket for
even one of the hash functions we use.

34
00:02:10,110 --> 00:02:13,550
To start, we have to agree
on how similar is similar.

35
00:02:13,550 --> 00:02:18,220
We pick the threshold t that is the
minimum value of Jaccard similarity for

36
00:02:18,220 --> 00:02:20,840
us to regard a pair of
signatures as similar.

37
00:02:23,190 --> 00:02:27,560
That is, in the ideal world, columns c and
d of the signature matrix M would be

38
00:02:27,560 --> 00:02:30,870
a candidate pair if and
only if their similarity was at least t.

39
00:02:33,650 --> 00:02:37,880
Remember that the similarity of signatures
is the fraction of components or

40
00:02:37,880 --> 00:02:41,010
rows of the signature matrix
M on which they agree.

41
00:02:42,010 --> 00:02:46,760
So we want columns c and d to be
a candidate pair if the fraction of rows

42
00:02:47,890 --> 00:02:52,050
i for which m of i and c and m of i and

43
00:02:52,050 --> 00:02:57,190
d are the same to be at least t.

44
00:02:58,190 --> 00:03:00,650
So we need to create some
number of hash functions and

45
00:03:00,650 --> 00:03:04,280
use each to hash the columns of
signature matrix M into buckets.

46
00:03:06,010 --> 00:03:08,530
And we need a trick to make sure
that similar signatures, or

47
00:03:08,530 --> 00:03:12,140
columns, are much more likely
to hash to the same bucket for

48
00:03:12,140 --> 00:03:15,620
one of these hash functions than
if the signatures are dissimilar.

49
00:03:17,010 --> 00:03:20,110
As we mentioned before, we're going
to regard a pair of signatures as

50
00:03:20,110 --> 00:03:24,180
a candidate pair if even one of the hash
functions puts them in the same bucket.

51
00:03:26,180 --> 00:03:29,690
So, here's the picture of how
the hash functions are created.

52
00:03:30,830 --> 00:03:32,960
The yellow area is the signature matrix M.

53
00:03:34,030 --> 00:03:37,210
Each column corresponds
to one signature and

54
00:03:37,210 --> 00:03:40,290
each row is one of the components
of all signatures.

55
00:03:40,290 --> 00:03:43,400
That is, each row was created by
applying to each of the underlying sets

56
00:03:43,400 --> 00:03:48,250
one of the minhash functions we use to
create the signatures in the first place.

57
00:03:50,170 --> 00:03:53,490
We divide the rows into b bands for
some number b.

58
00:03:54,600 --> 00:03:56,700
As a result, there are r rows per band,

59
00:03:56,700 --> 00:03:59,830
where b times r is the total
length of the signatures.

60
00:03:59,830 --> 00:04:04,120
That is, the number of main hash functions
we use to create the signatures.

61
00:04:04,120 --> 00:04:06,530
We're going to create one
hash function from each band.

62
00:04:07,820 --> 00:04:12,290
Remember, we divided the signature
matrix M into b bands of r rows each.

63
00:04:13,610 --> 00:04:16,120
From each band, we create a hash function.

64
00:04:16,120 --> 00:04:20,910
This hash function hashes the values that
a given column has in that band only.

65
00:04:22,410 --> 00:04:24,580
Ideally, we would make one bucket for

66
00:04:24,580 --> 00:04:29,612
each possible vector of b values that
a column could have in that band.

67
00:04:29,612 --> 00:04:33,110
That is, we'd like to have so
many buckets that the hash function is

68
00:04:33,110 --> 00:04:37,170
really the identity function, but
that is probably too many buckets.

69
00:04:37,170 --> 00:04:39,580
For example, if b equals 5 and

70
00:04:39,580 --> 00:04:42,860
the components of a signature
are 32-bit integers,

71
00:04:42,860 --> 00:04:49,870
then they would be 2 to the 5 times 32,
or 2 to the 160th power of buckets.

72
00:04:49,870 --> 00:04:54,380
We can't even look at all these buckets
to see what is in them at the end.

73
00:04:54,380 --> 00:04:57,260
So we'll probably want to pick
a number of buckets that is smaller,

74
00:04:57,260 --> 00:04:59,180
say, a million or a billion.

75
00:05:02,170 --> 00:05:06,700
As we said, we consider a pair of columns
and signatures to be a candidate pair if

76
00:05:06,700 --> 00:05:10,520
they are in the same bucket according to
the hash function for any of the bands.

77
00:05:12,200 --> 00:05:12,860
Put another way,

78
00:05:12,860 --> 00:05:16,920
the only way we can be sure a pair of
signatures will become a candidate pair

79
00:05:16,920 --> 00:05:21,010
is if they, if they have exactly the same
components in at least one of the bands.

80
00:05:22,410 --> 00:05:25,720
Notice that if most of the components
of two signatures agree,

81
00:05:25,720 --> 00:05:30,180
then there's a good chance that they
will have 100% agreement in some band.

82
00:05:30,180 --> 00:05:32,430
But if they have few components in common,

83
00:05:32,430 --> 00:05:36,080
then they are unlikely to
agree 100% in any band.

84
00:05:36,080 --> 00:05:40,380
We'll make the mathematics more precise
shortly, but that's the intuition.

85
00:05:40,380 --> 00:05:43,676
Given t, the threshold
Jaccard similarity needed for

86
00:05:43,676 --> 00:05:47,042
pairs to be considered similar,
we need to tune b and r so

87
00:05:47,042 --> 00:05:51,431
that most of the similar pairs
are 100% similar in at least one band.

88
00:05:51,431 --> 00:05:54,943
But few of the pairs with
the Jaccard similarity less than t

89
00:05:54,943 --> 00:05:57,028
are 100% similar in any band.

90
00:05:57,028 --> 00:06:00,464
The only constraint we have is that
b times r has to equal the length of

91
00:06:00,464 --> 00:06:01,790
the signatures.

92
00:06:01,790 --> 00:06:04,580
That is, equal to the number
of minhash functions we

93
00:06:04,580 --> 00:06:06,870
used to create the signatures
in the first place.

94
00:06:08,440 --> 00:06:14,140
In, intuitively, if we make b large and
r small, then there are lots of bands and

95
00:06:14,140 --> 00:06:18,180
therefore lots of opportunities for
a pair to wind up in the same bucket.

96
00:06:18,180 --> 00:06:21,180
And since r, the width of the band,
is small, it's not hard for

97
00:06:21,180 --> 00:06:24,380
a pair to hash to the same bucket for
one of the bands.

98
00:06:24,380 --> 00:06:26,670
Thus making b large is
good at the similari,

99
00:06:26,670 --> 00:06:29,650
if the similarity threshold
is relatively low.

100
00:06:30,670 --> 00:06:35,490
conversely, if you make b small and
r large, then it would be very hard for

101
00:06:35,490 --> 00:06:37,870
two signatures to hash
to the same bucket for

102
00:06:37,870 --> 00:06:42,865
a given band and there a few bands that
give them the opportunity to do so.

103
00:06:42,865 --> 00:06:47,555
Thus a small number of bands is best if
we have a high threshold of similarity.

104
00:06:47,555 --> 00:06:49,560
Again, we'll make
the math precise shortly.

105
00:06:52,470 --> 00:06:56,452
Before we go on, here's a picture of
what one of the hash functions for

106
00:06:56,452 --> 00:06:59,460
LSH on signature matrices looks like.

107
00:06:59,460 --> 00:07:04,150
We see one of the b bands,
the band consisting of r rows, of course.

108
00:07:04,150 --> 00:07:08,310
Oh, we also show the matrix
that's consisting of several,

109
00:07:08,310 --> 00:07:11,000
of seven columns or signatures.

110
00:07:11,000 --> 00:07:12,750
And each of the purple rep,

111
00:07:12,750 --> 00:07:17,942
rectangles represents the portion of its
column within the one band we focus on.

112
00:07:21,210 --> 00:07:25,330
Now, columns six and
seven hash to different buckets.

113
00:07:25,330 --> 00:07:27,590
Thus, they surely differ within this band,
so

114
00:07:27,590 --> 00:07:30,590
we are not motivated to compare them for
similarity.

115
00:07:30,590 --> 00:07:32,377
That is, the pair sex and

116
00:07:32,377 --> 00:07:37,690
seven is not made a candidate
pair by this LSH hash function.

117
00:07:37,690 --> 00:07:41,473
Perhaps column six and seven will hash
in the same bucket for some other hash

118
00:07:41,473 --> 00:07:44,974
function and will then therefore
become a candidate pair from whoa.

119
00:07:44,974 --> 00:07:46,524
But from what we can tell,

120
00:07:46,524 --> 00:07:50,614
looking only at this one hashing,
they do not form a candidate pair.

121
00:07:54,110 --> 00:07:58,260
On the other hand, columns two and
six do hash to the same bucket.

122
00:07:58,260 --> 00:07:58,820
So two and

123
00:07:58,820 --> 00:08:03,010
six is a candidate pair regardless
of what happens in the other bands.

124
00:08:03,010 --> 00:08:06,660
There's a good chance that columns two and
six are identical within the band shown.

125
00:08:08,186 --> 00:08:13,626
That is these pieces of their columns.

126
00:08:16,232 --> 00:08:18,454
Are identical.

127
00:08:18,454 --> 00:08:22,430
There's a small chance that these segments
of these columns are not identical, but

128
00:08:22,430 --> 00:08:25,170
they just happen to hash
to the same bucket.

129
00:08:25,170 --> 00:08:29,970
We will generally neglect that
probability as it can be made tiny,

130
00:08:29,970 --> 00:08:33,550
like 1 in 4 billion,
if we use 2 to the 32nd power buckets.

131
00:08:35,500 --> 00:08:37,900
Let's look at a particular
example to get a feel for

132
00:08:37,900 --> 00:08:41,950
how the probabilities of false positives
and negatives work out in practice.

133
00:08:44,350 --> 00:08:46,162
We'll assume there are 100,000 columns.

134
00:08:46,162 --> 00:08:48,097
That is, we're looking for

135
00:08:48,097 --> 00:08:52,630
similar documents among
a set of 100,000 documents.

136
00:08:52,630 --> 00:08:55,870
We'll assume signatures are of length 100.

137
00:08:55,870 --> 00:08:58,880
That is, we use the 100 minhash
functions to create the signatures.

138
00:08:58,880 --> 00:09:03,310
The signature matrix M is thus
100 rows by 100,000 columns.

139
00:09:06,000 --> 00:09:08,839
Notice that the signatures fit
very nicely in main memory.

140
00:09:08,839 --> 00:09:13,311
Assuming the components of
a signature are 4-byte integers,

141
00:09:13,311 --> 00:09:19,377
each signature takes 400 bytes and the
total space requirement is 40 megabytes.

142
00:09:19,377 --> 00:09:22,260
Now, let the similarity threshold be 80%.

143
00:09:22,260 --> 00:09:25,610
That is, we consider a pair
of signatures similar if and

144
00:09:25,610 --> 00:09:28,710
only if they agree in at least
80 of their 100 components.

145
00:09:30,600 --> 00:09:33,590
There are approximately 5
billion pairs to compare so

146
00:09:33,590 --> 00:09:37,180
we'd like to use LSH to avoid
having to compare them all.

147
00:09:37,180 --> 00:09:42,010
Incidentally, if you don't see why 5
billion is the approximate count of pairs,

148
00:09:42,010 --> 00:09:46,150
the exact number of pairs of items
chosen from a 100,000 items is

149
00:09:46,150 --> 00:09:47,955
a 100,000 choose two.

150
00:09:53,756 --> 00:10:02,553
Which is a 100,000 times
99,999 divided by 2.

151
00:10:02,553 --> 00:10:08,161
And if we approximate the five 9s by
a 100,000, we get exactly 5 billion.

152
00:10:13,915 --> 00:10:18,972
In our example, we're going to divide
the 100 rows of signatures ma,

153
00:10:18,972 --> 00:10:23,200
of the signature matrix into
20 bands with five rows each.

154
00:10:26,120 --> 00:10:28,550
First, let's consider two columns,
C1 and C2,

155
00:10:28,550 --> 00:10:32,660
that represent sets with
Jaccard similarity 0.8.

156
00:10:32,660 --> 00:10:36,860
Notice that because of the randomness
involved in minhashing, the columns C1 and

157
00:10:36,860 --> 00:10:40,110
C2 may agree in more or
fewer than 80 of their rows,

158
00:10:40,110 --> 00:10:43,150
but they'll most likely have
approximately 80 equal rows.

159
00:10:45,670 --> 00:10:49,250
Now, what is the probability that
these columns are 100% similar in

160
00:10:49,250 --> 00:10:49,789
one given band?

161
00:10:51,430 --> 00:10:55,270
Well, the probability that they
agree in any one row is exactly 0.8.

162
00:10:55,270 --> 00:10:58,470
Remember that the probability
that a minhash function agrees on

163
00:10:58,470 --> 00:11:03,320
two sets equals the Jaccard
similarity of the underlying sets.

164
00:11:03,320 --> 00:11:08,163
So the probability that the two columns
agree in all five of the rows of

165
00:11:08,163 --> 00:11:13,774
a band is 0.8 raised to the fifth power,
or approximately 0.328.

166
00:11:13,774 --> 00:11:16,623
That's not very high probability, but

167
00:11:16,623 --> 00:11:22,010
we have 20 chances to make the pair
of columns a candidate pair.

168
00:11:22,010 --> 00:11:30,220
The probability that they do
not hash to the same bucket

169
00:11:30,220 --> 00:11:38,441
in one band is 1 minus 0.328 or 0.672.

170
00:11:38,441 --> 00:11:39,160
Okay.

171
00:11:39,160 --> 00:11:44,936
But the probability that the columns
failed to hash to the same bucket for

172
00:11:44,936 --> 00:11:51,089
any of the 20 bands is that value
0.672 raised to the twentieth power,

173
00:11:51,089 --> 00:11:53,000
which is a tiny number.

174
00:11:53,000 --> 00:11:57,150
It's actually this 0.00035.

175
00:11:57,150 --> 00:12:02,790
The chance that pair C1 and C2 will

176
00:12:02,790 --> 00:12:12,005
be a candidate pair is 1 minus that,
or 0.99965.

177
00:12:12,005 --> 00:12:15,410
Put another way,
the probability of a false negative,

178
00:12:15,410 --> 00:12:18,816
a pair of sets that have
Jaccard similarity 80%, but

179
00:12:18,816 --> 00:12:24,704
whose signatures do not become a candidate
pair is 0.00035, or about 1 in 3,000.

180
00:12:27,050 --> 00:12:31,764
Now look at a pair of sets that
have Jaccard similarity 0.4.

181
00:12:31,764 --> 00:12:36,612
The probability their signatures
are identical in a given band is

182
00:12:36,612 --> 00:12:39,799
0.4 to the fifth power, or about 1%.

183
00:12:39,799 --> 00:12:44,354
The probability that their signatures hash
to the same bucket in at least one of

184
00:12:44,354 --> 00:12:48,160
the 20 bands is surely no more
than 20 times that, or 20%.

185
00:12:49,765 --> 00:12:50,820
that's, that's not great.

186
00:12:50,820 --> 00:12:54,410
It means that among 40%
similar underlying sets,

187
00:12:54,410 --> 00:12:59,420
there are 20% false positives, pairs of
signatures we will have to compare and

188
00:12:59,420 --> 00:13:05,820
yet will find that they're not
at least 80% silar, similar.

189
00:13:05,820 --> 00:13:10,900
But 20% false positives is bad,
but the false

190
00:13:10,900 --> 00:13:16,550
positive rate falls rapidly as the
similarity of underlying sets decreases.

191
00:13:16,550 --> 00:13:22,870
For example, for 20% Jaccard similarity,
we get less than 1% false positives.

192
00:13:22,870 --> 00:13:25,970
We cannot determine the exact number
of false positives because that

193
00:13:25,970 --> 00:13:30,720
depends on the distribution of Jaccard
Similarities among the underlying sets.

194
00:13:30,720 --> 00:13:35,120
For example,
if most pairs of sets were 79% similar,

195
00:13:35,120 --> 00:13:37,490
almost all would be false positives.

196
00:13:37,490 --> 00:13:41,373
But if the typical pair of sets has
a Jaccard similarity of a few percent,

197
00:13:41,373 --> 00:13:43,931
then there would be almost
no false positives.

198
00:13:47,908 --> 00:13:51,153
A way to look at the problem of
designing an LSH scheme from

199
00:13:51,153 --> 00:13:52,960
a minhash matrix is this.

200
00:13:52,960 --> 00:13:56,150
We want the probability of two
columns sharing a bucket to be

201
00:13:56,150 --> 00:13:58,670
a step function with threshold t

202
00:13:58,670 --> 00:14:02,810
equal to the value at which we
regard the underlying sets similar.

203
00:14:04,500 --> 00:14:09,870
That is, if the Jaccard similarity s
of the underlying sets is less than t,

204
00:14:09,870 --> 00:14:14,130
we want there to be zero chance
the signatures will share a bucket for

205
00:14:14,130 --> 00:14:18,070
one of the hashings and
thus become a candidate pair.

206
00:14:18,070 --> 00:14:21,190
However, if the underlying
Jaccard similarity exceeds 2,

207
00:14:21,190 --> 00:14:24,500
we want the pair of signatures
surely to become a candidate pair.

208
00:14:27,835 --> 00:14:31,790
On the other hand, what does a single
row of a signature matrix gives us?

209
00:14:31,790 --> 00:14:33,800
It gives us a straight line.

210
00:14:33,800 --> 00:14:36,490
The justification is the theorem
about the probability of

211
00:14:36,490 --> 00:14:41,530
two minhash values equaling the Jaccard
similarity of the underlying set.

212
00:14:41,530 --> 00:14:42,440
That's not too bad.

213
00:14:42,440 --> 00:14:45,780
At least the probability goes
in the right direction, but

214
00:14:45,780 --> 00:14:49,570
it does leave a lot of false positives and
negatives.

215
00:14:49,570 --> 00:14:54,357
That is, for a given threshold t,
all of these are false positives and

216
00:14:54,357 --> 00:14:56,965
all of these are all false negatives.

217
00:15:00,185 --> 00:15:05,764
But when we combine many minhash functions
into b bands of r rows each, we begin to

218
00:15:05,764 --> 00:15:12,490
get an s curve shape with greatly reduced
false positive and negative regions.

219
00:15:12,490 --> 00:15:16,460
We're going to derive the function that
relates the probability of two sets having

220
00:15:16,460 --> 00:15:21,410
the signatures become a candidate
pair to the similarity s of the sets.

221
00:15:23,490 --> 00:15:27,500
First, if the underlying sets
have Jaccard similarity s,

222
00:15:27,500 --> 00:15:30,960
then the probability that their
signatures will be identical in all

223
00:15:30,960 --> 00:15:33,900
r rows of one particular
band is s to the r.

224
00:15:36,310 --> 00:15:39,980
So the probability that their signatures
will not be equal in this band is

225
00:15:39,980 --> 00:15:41,110
1 minus s to the r.

226
00:15:44,360 --> 00:15:48,215
And the probability that their signatures
will be unequal in each of the b

227
00:15:48,215 --> 00:15:50,247
bands is that raised to the bth power.

228
00:15:54,074 --> 00:15:58,956
Finally, the probability that
their signatures will agree in at

229
00:15:58,956 --> 00:16:01,617
least one band is one minus that, or

230
00:16:01,617 --> 00:16:06,962
one minus the quantity, one minus s
to the r all raised to the bth power.

231
00:16:06,962 --> 00:16:08,150
Okay?

232
00:16:08,150 --> 00:16:12,239
As b and r get large, this function
increasingly resembles a step function.

233
00:16:15,090 --> 00:16:19,657
And the threshold at which the rise
occurs is approximately 1 over b

234
00:16:19,657 --> 00:16:21,830
raised to the power of 1 over r.

235
00:16:22,910 --> 00:16:26,867
For example,
in the case of b equals 20 and r equals 5,

236
00:16:26,867 --> 00:16:33,230
the threshold will be approximately the
fifth root of 120th, which is about 0.55.

237
00:16:36,478 --> 00:16:39,122
Here are some sample
values of this s curve for

238
00:16:39,122 --> 00:16:43,300
the case we have been examining,
20 bands of five rows each.

239
00:16:43,300 --> 00:16:47,390
It's not exactly a step function, but
it does get rather steep in the middle.

240
00:16:48,610 --> 00:16:52,479
For example,
looks at the values between 0.4 and 0.6.

241
00:16:54,030 --> 00:16:58,562
The rise from 0.4 to 0.6 is more than 0.6,
so

242
00:16:58,562 --> 00:17:01,998
the average slope in
this region is over 3.

243
00:17:01,998 --> 00:17:09,015
On the other hand, in the region 0 to 0.4,
the rise is less than 0.2 and

244
00:17:09,015 --> 00:17:14,280
the same can be said for
the region from 0.6 to 1.

245
00:17:14,280 --> 00:17:18,030
That is, the slope is less than
one-half in both these regions.

246
00:17:18,030 --> 00:17:22,699
So a rough approximation to this
curve looks like, like this.

247
00:17:26,064 --> 00:17:28,504
Okay, it's not exactly a step function,
but

248
00:17:28,504 --> 00:17:31,770
much better than the linear
function we got from a single row.

249
00:17:33,210 --> 00:17:36,190
So here's a summary of what we
need to do to find sets with

250
00:17:36,190 --> 00:17:39,730
a given threshold t of Jaccard similarity.

251
00:17:39,730 --> 00:17:43,330
First, we need to decide
on our values of b and r.

252
00:17:43,330 --> 00:17:47,340
As we mentioned, the threshold t
will be approximately 1 over b

253
00:17:47,340 --> 00:17:48,610
to the power of 1 over r.

254
00:17:48,610 --> 00:17:53,674
But there are many suitable values
of b and r for a given threshold.

255
00:17:53,674 --> 00:17:58,400
The larger we make b and r, that is,
the longer the signatures we use,

256
00:17:58,400 --> 00:18:01,270
the closer the s curve will
be to a step function.

257
00:18:02,580 --> 00:18:06,040
And therefore, the fewer false
positives and negatives we can have.

258
00:18:06,040 --> 00:18:08,890
But the longer we make the signatures,
the more space they will take and

259
00:18:08,890 --> 00:18:12,534
the more work it will be to
perform all the minhashing.

260
00:18:15,260 --> 00:18:18,680
Then we must run the LSH
to get the candidate pairs.

261
00:18:18,680 --> 00:18:21,190
For each candidate pair,
we examine their signatures and

262
00:18:21,190 --> 00:18:23,510
count the number of components
in which they agree.

263
00:18:25,130 --> 00:18:28,340
That way, we can determine whether
the similarity of the signatures really

264
00:18:28,340 --> 00:18:30,780
does reach or exceed the threshold t.

265
00:18:33,620 --> 00:18:36,820
We can rely on the similarity of
the signatures truly measuring the Jaccard

266
00:18:36,820 --> 00:18:39,940
similarity of the underlying sets.

267
00:18:39,940 --> 00:18:42,840
however, if we want to spend
the resources, we can go to

268
00:18:42,840 --> 00:18:48,330
the sets themselves after determining that
their signatures are sufficiently similar.

269
00:18:48,330 --> 00:18:51,100
In some cases, the similarity
of the soon con nutrids will

270
00:18:51,100 --> 00:18:54,790
overestimate the similarities of
the sets that they represent, so

271
00:18:54,790 --> 00:18:58,139
it is possible that the two sets
are not really similar enough.

272
00:18:58,139 --> 00:19:01,211
By computing the Jaccard
similarity of the underlying sets,

273
00:19:01,211 --> 00:19:03,170
we can eliminate the false positives.

274
00:19:04,610 --> 00:19:07,340
Unfortunately, we cannot eliminate
false negatives this way.

275
00:19:08,390 --> 00:19:11,655
If two sets have Jaccard
similarity above threshold, but

276
00:19:11,655 --> 00:19:15,451
by bad luck, their signatures
never become a candidate pair,

277
00:19:15,451 --> 00:19:19,732
then we'll never look at this pair of
signatures or their underlying sets.