This report describes our experiments on document similarity and candidate pair detection using Min-Hashing and Locality Sensitive Hashing (LSH) on two types of datasets: a set of text documents (D1–D4) and the MovieLens 100k dataset. For each task, we outline the goals, describe the key functions (with brief argument descriptions), present a summary of the outputs, and analyze the observations.
To run task number x
g++ task_x.cpp -o a && ./a- Generate k-grams:
- Character 2-grams and 3-grams for each document.
- Word 2-grams for each document.
- Compute distinct counts per document.
- Compute pairwise Jaccard similarities for the three types of k-grams.
readFile(filename: string) -> string
Reads the complete contents of a file into a string.getCharKGrams(text: string, k: int) -> set<string>
Generates distinct character k-grams from the text.splitIntoWords(text: string) -> vector<string>
Splits a text string into words.getWordKGrams(text: string, k: int) -> set<string>
Generates distinct word k-grams.jaccardSimilarity(set1: set<string>, set2: set<string>) -> double
Computes the Jaccard similarity as the size of the intersection divided by the union.
-
Distinct k-gram counts:
Document Char 2-grams Char 3-grams Word 2-grams D1.txt 263 765 279 D2.txt 262 762 278 D3.txt 269 828 337 D4.txt 255 698 232 -
Jaccard Similarity (selected pairs):
- Character 2-grams: Similarity between D1 and D2 is very high (\approx0.98).
- Character 3-grams: Notice a drop for pairs such as D1 vs D4 (\approx0.3051).
- Word 2-grams: A dramatic decrease in similarity for dissimilar documents (e.g., D1 vs D4 \approx0.0302).
- Consistency:
The high similarity between D1 and D2 across all types indicates that these documents share nearly identical content. - Sensitivity:
The 3-gram similarity is lower for some pairs, showing that finer granularity (3-character grams) can better discriminate differences between documents. - Semantic Differences:
Word 2-grams capture a more semantic level, where dissimilar documents have extremely low similarity values.
- Estimate Jaccard similarity using Min-Hashing.
We use different numbers of hash functions (t = {20, 60, 150, 300, 600}) and run each experiment 10 times. - Report average similarity and time.
generateHashFunctions(t: int) -> vector<HashFunction>
Generates a family of random hash functions.computeMinhashSignature(kgrams: set<string>, hashFunctions: vector<HashFunction>) -> vector<int>
Computes the min-hash signature for a document.computeMinhashSimilarity(sig1: vector<int>, sig2: vector<int>) -> double
Compares two signatures position-by-position.
-
Average Similarity and Time:
t Avg. Similarity Avg. Time (μs) 20 0.9800 191.9 60 0.9817 471.0 150 0.9820 979.5 300 0.9743 1816.8 600 0.9800 3747.3
- Accuracy vs. Time Trade-Off:
While the similarity estimates are very high (reflecting the high overlap in the documents), increasingtleads to longer computation times. - Variance:
Even with fewer hash functions (e.g., t=20), the estimates remain stable, indicating that the documents are very similar.
- Hyperparameter Tuning for LSH:
For a fixed signature lengtht = 160, we search over all possible combinations wherer * b = 160.
We choose the best parameters based on the steepness of the S-curve (i.e., maximum derivative at τ = 0.7). - Compute LSH candidate probability for each document pair using the tuned parameters.
candidateProbability(s: double, r: int, b: int) -> double
Computes ( f(s) = 1 - (1 - s^b)^r ) for a given similarity ( s ).derivativeAt(s: double, r: int, b: int) -> double
Computes the derivative ( f'(s) ) used for tuning.tuneHyperparameters(t: int, tau: double, &best_r: int, &best_b: int, &best_f_at_tau: double)
Iterates over candidate (r, b) values to pick the best based on the derivative at τ.
-
Tuned Parameters:
- Best parameters: r = 20, b = 8
- f(0.7): Approximately 0.6950
-
LSH Candidate Probabilities (using 3-grams):
Document Pair Exact Jaccard Candidate Probability D1 vs D2 0.9780 1.0000 D1 vs D3 0.5804 0.2282 D1 vs D4 0.3051 0.0015 D2 vs D3 0.5680 0.1959 D2 vs D4 0.3059 0.0015 D3 vs D4 0.3121 0.0018
- Tuning Outcome:
The best parameters (r = 20, b = 8) provide a steep transition around the threshold of 0.7. - Probability Trends:
Document pairs with high exact similarity (like D1 vs D2) have candidate probabilities of 1.0. In contrast, pairs with low similarity have almost zero chance of being selected. - Design Insight:
Tuning based on the derivative helps in achieving a clear separation at the target threshold, ensuring that candidate selection is robust.
- Compute exact Jaccard similarities between users based on the set of movies rated.
- Identify pairs with similarity ≥ 0.5.
- Apply Min-Hashing with t = 50, 100, and 200 hash functions to estimate similarities.
- Report false positives and false negatives (averaged over 5 runs).
loadMovieLensData(filename: string, numUsers: int) -> vector<set<int>>
Loads and processes MovieLens data, building a set of rated movies per user.computeMinhashSignature(userMovies: set<int>, hashFunctions: vector<HashFunction>) -> vector<int>
Computes the min-hash signature for a user.jaccardSimilarity(s1: set<int>, s2: set<int>) -> double
Computes the exact Jaccard similarity between users.computeApproxSimilarity(sig1: vector<int>, sig2: vector<int>) -> double
Computes similarity based on min-hash signatures.
-
Exact Similarity (Threshold ≥ 0.5):
10 candidate user pairs were found (e.g., Users (197, 600) with similarity = 0.5000, Users (408, 898) with similarity = 0.8387). -
Min-Hash Results:
- t = 50:
- Total candidate pairs in first run: 125
- Average False Positives: 102.6
- Average False Negatives: 2.0
- t = 100:
- Total candidate pairs: 23
- Average False Positives: 39.2
- Average False Negatives: 2.4
- t = 200:
- Total candidate pairs: 12
- Average False Positives: 8.4
- Average False Negatives: 2.4
- t = 50:
- Trade-Off in t:
Increasing the number of hash functions significantly reduces false positives (from 102.6 with t = 50 to 8.4 with t = 200), thereby increasing precision. - False Negatives:
The false negatives remain relatively low across different t values, indicating that true similar pairs are consistently captured. - Practical Insight:
For applications where false positives are costly, higher t values (e.g., t = 200) are preferable even if they require more computation.
- Implement LSH by breaking up the signature table into bands.
- Test various configurations for t = 50, 100, and 200 hash functions with different (r, b) combinations.
- Report average false positives and negatives for thresholds of 0.6 and 0.8 (over 5 runs).
runLSH(signatures: vector<vector<int>>, r: int, b: int) -> set<pair<int,int>>
Performs banding on the signature table and returns candidate pairs.loadMovieLensData(filename: string, numUsers: int) -> vector<set<int>>
(As in Task 4) Loads the MovieLens data.jaccardSimilarity(s1: set<int>, s2: set<int>) -> double
Computes the exact similarity for ground-truth comparisons.
-
Experiment Summary:
Experiment Threshold Avg. False Positives Avg. False Negatives t = 50, r = 5, b = 10 0.6 1.40 2.80 0.8 1.40 0.80 t = 100, r = 5, b = 20 0.6 0.00 3.00 0.8 0.00 1.00 t = 200, r = 5, b = 40 0.6 0.00 3.00 0.8 0.00 1.00 t = 200, r = 10, b = 20 0.6 0.00 2.60 0.8 0.00 0.60
- Threshold Effects:
With a higher threshold (0.8), false negatives decrease as fewer pairs are expected to be similar, while false positives remain low. - Configuration Impact:
For t = 200, the configuration with r = 10, b = 20 performs slightly better (fewer false negatives) than r = 5, b = 40. - Robustness:
The LSH approach successfully prunes non-similar pairs while retaining most true similar pairs, especially for higher t values and stricter banding configurations.
-
Task 1:
k-gram analysis shows that character-based grams capture high overlap for similar documents, while word-based grams emphasize semantic differences. This informs the choice of similarity measure based on application needs. -
Task 2:
Min-Hashing provides stable similarity estimates even with a relatively low number of hash functions. However, higher values improve precision at the cost of increased computation time. -
Task 3:
Hyperparameter tuning for LSH is critical. Our tuning based on the derivative at τ = 0.7 yielded (r, b) = (20, 8), which effectively separates similar from dissimilar pairs. The candidate probability function confirms that only highly similar document pairs (e.g., D1 vs D2) are likely to be selected. -
Task 4 & 5:
On the MovieLens dataset, Min-Hashing and LSH experiments show that higher t values reduce false positives, and careful banding (i.e., selection of r and b) further refines candidate selection. LSH results indicate that while false positives can be minimized to nearly zero, false negatives vary with the similarity threshold and band configuration.
This series of experiments demonstrates how probabilistic techniques like Min-Hashing and LSH can be fine-tuned to balance efficiency and accuracy in large-scale similarity search problems. Our approach, based on careful hyperparameter tuning and multiple evaluations, provides insights into practical trade-offs in real-world applications.