3.3. SIMILARITY-PRESERVING SUMMARIES OF SETS
85
(b) However, if c has 1 in row r, then for each i = 1, 2, . . . , n set SIG(i, c)
to the smaller of the current value of SIG(i, c) and hi(r).
Row
S1
S2
S3
S4
x + 1 mod 5
3x + 1 mod 5
0
1
0
0
1
1
1
1
0
0
1
0
2
4
2
0
1
0
1
3
2
3
1
0
1
1
4
0
4
0
0
1
0
0
3
Figure 3.4: Hash functions computed for the matrix of Fig. 3.2
Example 3.8 : Let us reconsider the characteristic matrix of Fig. 3.2, which
we reproduce with some additional data as Fig. 3.4.
We have replaced the
letters naming the rows by integers 0 through 4. We have also chosen two hash
functions: h1(x) = x+1 mod 5 and h2(x) = 3x+1 mod 5. The values of these
two functions applied to the row numbers are given in the last two columns of
Fig. 3.4. Notice that these simple hash functions are true permutations of the
rows, but a true permutation is only possible because the number of rows, 5, is
a prime. In general, there will be collisions, where two rows get the same hash
value.
Now, let us simulate the algorithm for computing the signature matrix.
Initially, this matrix consists of all ∞’s:
S1
S2
S3
S4
h1
∞
∞
∞
∞
h2
∞
∞
∞
∞
First, we consider row 0 of Fig. 3.4. We see that the values of h1(0) and
h2(0) are both 1. The row numbered 0 has 1’s in the columns for sets S1 and
S4, so only these columns of the signature matrix can change. As 1 is less than
∞, we do in fact change both values in the columns for S1 and S4. The current
estimate of the signature matrix is thus:
S1
S2
S3
S4
h1
1
∞
∞
1
h2
1
∞
∞
1
Now, we move to the row numbered 1 in Fig. 3.4. This row has 1 only in
S3, and its hash values are h1(1) = 2 and h2(1) = 4. Thus, we set SIG(1, 3) to 2
and SIG(2, 3) to 4. All other signature entries remain as they are because their
columns have 0 in the row numbered 1. The new signature matrix:
S1
S2
S3
S4
h1
1
∞
2
1
h2
1
∞
4
1
