Database Reference
In-Depth Information
For each pair, what is the estimated angle between them, according to the sketches? What
are the true angles?
EXERCISE
3.7.3 Suppose we form sketches by using all sixteen of the vectors of length 4,
whose components are each +1 or −1. Compute the sketches of the three vectors in
Ex-
ercise 3.7.2
.
How do the estimates of the angles between each pair compare with the true
angles?
EXERCISE
3.7.4 Suppose we form sketches using the four vectors from
Exercise 3.7.2
.
!
(a) What are the constraints on
a
,
b
,
c
, and
d
that will cause the sketch of the vector [
a,
b, c, d
] to be [+1
,
+1
,
+1
,
+1]?
!!
(b) Consider two vectors [
a, b, c, d
] and [
e, f, g, h
]. What are the conditions on
a, b, . .
. , h
that will make the sketches of these two vectors be the same?
EXERCISE
3.7.5 Suppose we have points in a 3-dimensional Euclidean space:
p
1
= (1
,
2
,
3),
p
2
= (0
,
2
,
4), and
p
3
= (4
,
3
,
2). Consider the three hash functions defined by the three
axes (to make our calculations very easy). Let buckets be of length
a
, with one bucket the
interval [0
, a
) (i.e., the set of points
x
such that 0 ≤
x
<
a
), the next [
a,
2
a
), the previous one
[−
a,
0), and so on.
(a) For each of the three lines, assign each of the points to buckets, assuming
a
= 1.
(b) Repeat part (a), assuming
a
= 2.
(c) What are the candidate pairs for the cases
a
= 1 and
a
= 2?
!
(d) For each pair of points, for what values of
a
will that pair be a candidate pair?
3.8 Applications of Locality-Sensitive Hashing
In this section, we shall explore three examples of how LSH is used in practice. In each
case, the techniques we have learned must be modified to meet certain constraints of the
problem. The three subjects we cover are:
(1)
Entity Resolution
: This term refers to matching data records that refer to the same real-
world entity, e.g., the same person. The principal problem addressed here is that the
similarity of records does not match exactly either the similar-sets or similar-vectors
models of similarity on which the theory is built.
