Asmt 3: Distances and LSH

Asmt 3: Distances and LSH

100 points
Overview
In this assignment you will explore LSH and Euclidean distances.
You will use a data set for this assignment:
• http://www.cs.utah.edu/˜jeffp/teaching/cs5140/A3/R.csv
It is recommended that you use LaTeX for this assignment (or other option that can properly digitally
render math). If you do not, you may lose points if your assignment is difficult to read or hard to follow.
Find a sample form in this directory: http://www.cs.utah.edu/˜jeffp/teaching/latex/
1 Choosing r, b (35 points)
Consider computing an LSH using t = 160 hash functions. We want to find all object pairs which have
Jaccard similarity above τ = .85.
A: (15 points) Use the trick mentioned in class and the notes to estimate the best values of hash functions
b within each of r bands to provide the S-curve
f(s) = 1 − (1 − s
b
)
r
with good separation at τ . Report these values.
B: (15 points) Consider the 4 objects A, B, C, D, with the following pair-wise similarities:
A B C D
A 1 0.77 0.25 0.33
B 0.77 1 0.20 0.55
C 0.25 0.20 1 0.91
D 0.33 0.55 0.91 1
Using your choice of r and b and f(·), what is the probability of each pair of the four objects for being
estimated to having similarity greater that τ = 0.85? Report 6 numbers. (Show your work.)
2 Generating Random Directions (30 points)
A: (10 points) Describe how to generate a single random unit vector in d = 10 dimensions using only the
operation u ← unif(0, 1) which generates a uniform random variable between 0 and 1. (This can be called
multiple times.)
B: (20 points) Generate t = 160 unit vectors in R
d
for d = 100. Plot of cdf of their pairwise dot products
(yes, you need to calculate
t
2
?
dot products).
CS 6140/CS 5140 Data Mining; Spring 2020 Instructor: Jeff M. Phillips, U. of Uta
3 Angular Hashed Approximation (35 points)
Consider the n = 500 data points in R
d
for d = 100 in data set R, given at the top. We will use the angular
similarity, between two vectors a, b ∈ R
d
:
sang(a, b) = 1 −
1
π
arccos(ha, ¯
¯bi)
If a, b are not unit vectors (e.g., in S
d−1
), then we convert them to a¯ = a/kak2 and ¯b = b/kbk2. The
definition of sang(a, b) assumes that the input are unit vectors, and it takes a value between 0 and 1, with as
usual 1 meaning most similar.
A: (15 points) Compute all pairs of dot products (Yes, compute
n
2
?
values), and plot a cdf of their angular
similarities. Report the number with angular similarity more than τ = 0.85.
B: (20 points) Now compute the dot products and angular similarities among
t
2
?
pairs of the t random
unit vectors from Q2.B. Again plot the cdf, and report the number with angular similarity above τ = 0.85.
4 Bonus (3 points)
Implement the banding scheme with your choice of r, b, using your t = 160 random vectors, to estimate the
pairs with similarity above τ = 0.85 in the data set R. Report the fraction found above τ = 0.85. Compare
the runtime of this approach versus a brute force search.