Scalable Analytics: Chapter 2

High-Dimensional Data and the Problem of Finding Similar Items

Identifying similar items is a foundational challenge in scalable analytics, particularly when dealing with massive datasets and high-dimensional spaces. This problem, often exemplified by the Scene Completion Problem where the goal is to find the 10 nearest neighbors from a collection of 2 million images, appears in numerous domains:

• Duplicate Document Detection: Finding pages with similar words or classifying them by topic to identify duplicates.

• Recommendation Systems: Identifying customers who purchased similar products or products with similar customer sets.

• Visual Analysis: Identifying images with similar features.

• Web Analysis: Tracking users who visited similar websites.

Mathematically, the goal is defined as follows: given high-dimensional data points $\mathbf{x_1, x_2, \dots}$ (such as an image represented as a long vector of pixel colors) and a distance function $d(\mathbf{x_1, x_2})$ that quantifies the distance between them, find all pairs of points $(\mathbf{x_i, x_j})$ such that $d(\mathbf{x_i, x_j}) \le s$, where $s$ is a specific distance threshold.

Distance Measures and Jaccard Similarity

For any application, the definition of "distance" must be established first. A primary measure used for sets is the Jaccard similarity and Jaccard distance.

• Jaccard Similarity: The similarity of two sets $C_1$ and $C_2$ is the size of their intersection divided by the size of their union:     $sim(C_1, C_2) = \frac{|C_1 \cap C_2|}{|C_1 \cup C_2|}$     Example: If two sets have 3 elements in their intersection and 8 in their union, the Jaccard similarity is $\frac{3}{8}$.

• Jaccard Distance: This is the complement of the similarity measure:     $d(C_1, C_2) = 1 - sim(C_1, C_2) = 1 - \frac{|C_1 \cap C_2|}{|C_1 \cup C_2|}$     Example: Using the similarity above, the Jaccard distance is $\frac{5}{8}$.

The Three-Step Process for Scalable Similarity Analytics

Processing massive datasets (e.g., 1 million documents) na\u00efvely would require computing pairwise Jaccard similarities for every possible pair. For $N = 10^6$, this results in $\frac{N(N-1)}{2} \approx 5 \times 10^{11}$ comparisons. Assuming a speed of $10^6$ comparisons per second, this task would take approximately 5 days. To optimize this, three steps are employed:

1. Shingling: Converting documents into sets.

2. Min-Hashing: Converting large sets to short signatures while preserving similarity.

3. Locality-Sensitive Hashing (LSH): Focusing only on pairs of signatures likely to be from similar documents (candidate pairs).

Document Representation through Shingling

A k-shingle (or k-gram) for a document is a sequence of $k$ tokens that appears within the text. These tokens may be characters, words, or other units depending on the specific application.

• Example (k=2): For document $D_1 = abcab$, the set of 2-shingles is $S(D_1) = \{ab, bc, ca\}$.

• Shingle Bags: Shingles can be treated as a multiset (bag), where counts are preserved ($S'(D_1) = \{ab, bc, ca, ab\}$).

• Shingle Compression: To manage memory, long shingles can be hashed to a fixed size, such as 4 bytes. A document is then represented by the set of these hash values.

• Working Assumption: Documents sharing many shingles have similar text. However, the value of $k$ must be large enough to prevent unrelated documents from appearing similar due to common short shingles.

Min-Hashing and the Creation of Signatures

Sets can be encoded as 0/1 boolean vectors where each dimension represents an element in the universal set. These are organized into a boolean matrix where rows represent elements (shingles) and columns represent sets (documents). A value of 1 in row $e$ and column $s$ indicates that element $e$ is a member of set $s$.

Because boolean matrices are too large to compare in RAM, they are hashed into small signatures $h(C)$. The goal of Min-Hashing is to ensure that if $sim(C_1, C_2)$ is high, there is a high probability that $h(C_1) = h(C_2)$.

The Min-Hash Procedure

1. Imagine the rows of the boolean matrix are permuted under a random permutation $\pi$.

2. Define the hash function $h_\pi(C)$ as the index of the first row (in the permuted order) in which column $C$ has a value of 1:     $h_\pi(C) = \text{argmin } \pi(C)$

3. Create a signature of a column by using several (e.g., 100) independent random permutations/hash functions. The signature is a short integer vector.

The Min-Hash Property

For a random permutation $\pi$, the probability that the min-hash values for two columns are equal is exactly their Jaccard similarity: $Pr[h_\pi(C_1) = h_\pi(C_2)] = sim(C_1, C_2)$ This holds true because any shingle $y$ in the union $C_1 \cup C_2$ is equally likely to be the first element in the permuted order. The probability that this element belongs to both sets (the intersection) determines the equality of the min-hash.

Locality-Sensitive Hashing (LSH) for Candidate Detection

LSH aims to avoid the $O(N^2)$ comparison problem by hashing columns of the signature matrix $M$ such that similar columns hash to the same bucket with high probability. These become "candidate pairs."

Partitioning into Bands

The signature matrix $M$ is divided into $b$ bands, with each band containing $r$ rows.

1. For each band, the portion of each column is hashed to a hash table with many buckets.

2. Candidate pairs are those columns that hash to the same bucket in at least one band.

3. The parameters $b$ and $r$ are tuned to maximize the capture of similar pairs while minimizing false positives.

Mathematical Analysis of the LSH S-Curve

If columns $C_1$ and $C_2$ have similarity $t$, the probability of their signatures being shared in a bucket is as follows:

• Probability that all rows in a specific band of $r$ rows are equal: $t^r$

• Probability that at least one row in a band differs: $1 - t^r$

• Probability that no band is identical across all $b$ bands: $(1 - t^r)^b$

• Probability that at least one band is identical (the probability of being a candidate pair):     $P(\text{candidate pair}) = 1 - (1 - t^r)^b$

Performance Examples (b=20, r=5)

• 80% Similarity ($t = 0.8$):

  • Prob. identical in one band: $(0.8)^5 = 0.328$

  • Prob. NOT a candidate pair: $(1 - 0.328)^{20} = 0.00035$

  • Conclusion: Almost all highly similar pairs are caught.

• 30% Similarity ($t = 0.3$):

  • Prob. identical in one band: $(0.3)^5 = 0.00243$

  • Prob. BECOMING a candidate pair: $1 - (1 - 0.00243)^{20} \approx 0.0474$

  • Conclusion: Low similarity pairs are effectively filtered.

Generalized Locality-Sensitive Hash Families

LSH can be generalized beyond Jaccard similarity to other distance measures (e.g., Cosine distance, Euclidean distance). A distance measure $d(\cdot)$ is valid if it satisfies:

1. $d(x, y) \ge 0$

2. $d(x, y) = 0$ iff $x = y$

3. $d(x, y) = d(y, x)$

4. $d(x, y) \le d(x, z) + d(z, y)$ (Triangle Inequality)

A family $H$ of hash functions is $(d_1, d_2, p_1, p_2)$-sensitive if for any $x, y$:

• If d(x, y) < d_1, then $Pr[h(x) = h(y)] \ge p_1$

• If d(x, y) > d_2, then $Pr[h(x) = h(y)] \le p_2$

Amplification of Hash Families

To improve the S-curve effect (narrowing the transition between high and low probability), two constructions are used:

• AND Construction: Consists of $r$ functions. The combined function matches only if all $r$ functions match. It transforms the family into $(d_1, d_2, p_1^r, p_2^r)$-sensitive. This shrinks probabilities, pushing lower probabilities toward 0.

• OR Construction: Consists of $b$ functions. The combined function matches if at least one of the $b$ functions matches. It transforms the family into $(d_1, d_2, 1-(1-p_1)^b, 1-(1-p_2)^b)$-sensitive. This grows probabilities, pushing higher probabilities toward 1.

By composing an r-way AND followed by a b-way OR, the transformation of similarity $s$ results in the probability $1 - (1 - s^r)^b$. Conversely, a b-way OR followed by an r-way AND results in $1 - (1 - s^b)^r$.