Description
In this assignment, we will consider the problem of using LSH to find similar users, based on the fraction
of the movies they have watched in common. You are asked to write a Spark Python program which
uses LSH to efficiently find similar users.
A. Problem
Suppose there are 100 different movies, numbered from 0 to 99. A user is represented as a set of
movies. Jaccard coefficient is used to measure the similarity of sets.
Apply minhash to obtain a signature of 20 values for each user. Recall that this is done by
“logically” permuting the rows of characteristic matrix of movie-user matrix (i.e., row are movies
and columns represent users).
Assume that the i-th hash function for the signature: h(x,i) = (3x + 13i) % 100, where x is the
original row number in the matrix.
Apply LSH to speed up the process of finding similar users, where the signature is divided into 5
bands, with 4 values in each band.
Finding similar users: Based on the LSH result, for each user U, find top-5 users who are most
similar to U (by their Jaccard similarity, if same, choose the user that has smallest ID). If there
aren’t 5 similar users, e.g. U2 is only similar with U5, U9, U10, just output U2:U5,U9,U10.
Computation of signatures, LSH, and Jaccard similarities of similar users need to be done in
parallel.
o Hint: While computing LSH, you could take the signatures of one band as key, the user
ID as value, and then find the candidate pairs.
B. Input format
You are provided with a file where each line represents a user (with ID “U1” for example) and a list
of movies the user has watched (e.g., movie #0, 12, 45). Each user has watched at least one
movie.
U1,0,12,45
U2,2,3,5,99
…
INF 553 – Spring 2017
2
C. Output format
For each user with that we could find similar users, output their top-5 similar users as follows.
U2:U9,U10
U3:U8
U8:U3
…
Users should be output in the increasing order of the integer part (e.g., 1, 5, 10) of their IDs (e.g.,
U1, U5, U10).
Similar users for each user are ordered in the same way. If there are not 5 similar users after
applying LSH, i.e. U2 is only similar with U9, U10, output all them (U9, U10).
Format of execution:
bin/spark-submit __ lshrec.py input.txt output.txt
D. Time limit
Your program will be graded on a c4.2xlarge EC2 instance, and need to output result within 1 hour
for each test case. The largest test case would be as large as the attached
examples_test_cases/case_l/input.txt
E. Submission
Submit a Python script in the form: john_smith_lshrec.py, that is, your first and last names followed
by the name of program.
F. Notes
1. DO NOT use fixed input/output path. Read them from program arguments. The program
takes 2 arguments:
a. Path to input file
b. Path to output file
2. You must use the minHash functions, b, and p values provided in the instructions, or your
output would be different from the standard solution.
3. Make sure you follow the output format and the submission naming format. If you don’t
follow either one or both of them, 20% points will be deducted.
4. We will be using Moss for plagiarism detection. Do not copy from each other or you will
face serious consequences!
