Question

[Question 3, 12 points total, including 3.1-3.2] (minhasbing) Consider the following matrix, d1 0 d4 0 1 1 4 6 1 3 5 2 0 0 1 0 d2 1 0 1 0 0 1 d3 1 1 0 1 1 0 0 0 0 where each column represents a document (altogether we have 4 documents, di, d2, d3 and d4), and the number of rows is the size of the universal word set. Note the first column, ie, column (4, 6, 1, 3, 5, 2), represents a minhash permutation of the rows. 3.1 (8 points) calculate the minhash values for all the 4 documents using the given minbash permutation. No need to show the details of your calculation, simply write down the minhash value for each document: minhash value for di: minhash value for d2: minhash value for d3: minhash value for d4: 3.2 (4 points) Select ALL the correct statements about minhashing: a. the goal of performing minhashing of the data is to "shrink" the original huge dataset, so we can fit it to the cluster computing model b. minhashing helps us to calculate Jaccard distances with more precision each minhash function only creates one row in the signature matrix d. the input data matrix for minhashing does not have to be coded by using 0/1 only, it can be any integers or any float numbers, such as TF.IDF values c. your answer:

Answer 1

3.1 We will start be computing the minhash value of document d1 according to the minhash function. The first column, which is the column for document d1, has 0 in row 4, so we proceed to row 6, the second permuted order. The row 6 gives 1.

=> h(d1) = 6

Similarly

=> h(d2) = 4

=> h(d3) = 4

=> h(d4) = 6

3.2 Correct statements are

a) the goal of performing minhashing of the data is to “shrink” the original huge dataset, so we can fit it to the cluster computing model

c) each minhash function only creates one row in the signature matrix