294 - 333: Similarity Search in High Dimensions

Question 1

What is the Curse of Dimensionality?

Answer 1

It refers to the phenomenon where increasing the number of dimensions in data makes indexing and search increasingly inefficient, as distances between points tend to become indistinguishable.

Question 2

What is the Jaccard Coefficient?

Answer 2

Jaccard Coefficient measures the similarity between two sets
A and B, calculated as J(A,B) = |A ∩ B / A ∪ B|

Question 3

What is Locality Sensitive Hashing (LSH)?

Answer 3

LSH is an approximate hashing technique used to process similarity searches in high-dimensional spaces by grouping similar items into the same hash buckets.

Question 4

In Min Hashing, the probability that the minimum hash value of two sets is the same is equivalent to which metric?
a) Euclidean Distance
b) Manhattan Distance
c) Jaccard Coefficient
d) Cosine Similarity

Answer 4

c) Jaccard Coefficient

Question 5

How does Min Hashing approximate the Jaccard Coefficient?

Answer 5

By computing the smallest hash values of elements in sets and estimating similarity based on the proportion of identical hash values.

Question 6

Why might Locality Sensitive Hashing (LSH) use multiple hash tables?

Answer 6

To increase the likelihood that similar objects will collide in at least one bucket, improving search accuracy.