Databases Reference
In-Depth Information
(b) [−2, 3,−4, 5].
(c) [2,−3, 4,−5].
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 Exercise 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 Exer-
cise 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, 2a), 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.
