Chapter 3 & 4: Matching

Question 1

Applications set similarity

Answer 1

• Entity resolution
• Pages with similar words
• Netflix movies (similar tastes)
• Dual: movies with similar sets of fans

Question 2

Goal on finding similar documents

Answer 2

Given a large number of documents, find near duplicate pairs

Question 3

Problem of finding similar docs

Answer 3

• too many documents to compare all pairs
• Documents are too large or too many -> cannot fit in main memory
• Many small pieces of one document can appear out of order (order is important)

Question 4

Shingling

Answer 4

Generating a set of strings of length k that appear in the document

A k −shingle (or k −gram) for a document is a sequence
of k characters or k works or any other token
§ Example: k=2; doc = abcab. Doc2=abfef
§ Set of 2−shingles= {ab, bc, ca}. 2-shingles2={ab bf fe ef}
§ [ab bc ca bf fe ef]
§ D1: [1,1,1,0,0,0]. D2: [1,0, 0, 1,1,,1]

Question 5

Shingling benefits

Answer 5

• Documents that are similar will have many shingles in common
• Changing a word only affects k-shingles within distance k from the word
• Reordering paragraphs only affects the 2k shingles that cross paragraph boundaries

Question 6

Challenges using shingles

Answer 6

• Selecting the right k
• Selecting the rihjt token
• Hashing shingles

Question 7

Computing similarities between document representation as sets with Jaccard

Answer 7

Jacc (C1,C2) = |C1 intersection C2|/|C1 union C2|
But inefficient for large sets of documents because of pair-wise

Question 8

Similarity problems

Answer 8

Finsing subsets that have significant intersection

Question 9

Minhashing

Answer 9

Using techniques like minhashing allows for efficient computation of similarities among large datasets. By reducing the size of the data through the creation of signatures, we can achieve significant performance improvements without sacrificing the accuracy of similarity measurements. This approach is crucial for handling large-scale data efficiently.

Question 10

Matrix sparsity

Answer 10

In large datasets, the boolean matrix is typically sparse, meaning most entries are 0. This happens because each set (document) typically contains only a small subset of the universal set (all possible elements).

Question 11

Boolean Matrix Representation

Answer 11

Efficiently encodes sets as columns in a matrix, with rows representing elements of the universal set.

Question 12

Row hashing

Answer 12

Row hashing utilizes hash functions to induce random permutations of row indices. This approach allows for the generation of min-hash signatures without the need for explicit row permutations, thereby avoiding the associated storage and computational challenges. The one-pass implementation involves iterating through each row of the matrix, computing hash values for each row, and updating the min-hash values for each column based on the hash results. This strategy offers a scalable solution for efficiently computing min-hash signatures while avoiding the complexities of directly permuting large matrices.

Question 13

Localy-sensitive hashing (LSH)

Answer 13

Focus on pairs of signatures likely to be similar
1. create a shortlist of potential pairs that need to be checked for similarity.

2. Divide the columns into many groups using hashing. Elements within the same group are considered potential pairs that require comparison to determine their similarity

Question 14

Modern entity linking

Answer 14

Schema alignment -> blocking -> matching -> clustering