Set of tasks solved in Big Data Algorithms course at WUST. The main literature this course is based on, includes: "Mining of massive datasets" by J. Leskovec, A. Rajaraman and J. Ullman. Please consider the information below as my own notes for this course. For more details, I encourage you to look at the mentioned book.
Write the procedure with the interface jaccard(f1:String,f2:String,k:Integer):Double which for the files named f1 and f2 determines their k-shingles and then calculates their Jaccard distance. Before determining k-shingles, the files should be cleaned (the minimum is to delete new line characters, tabs and double spaces).
Apply the min-hash method to the previous problem (Problem A). Your procedure should depend on the H parameter, which determines the number of hash functions used to build the signature. Test this procedure on the data from the previous problem for H ∈ {50, 100, 250} and compare the Jaccard distance approximation with its exact values. Remember to generate a shared family of hash functions for all analyzed texts.
Jaccard Similarity is the measure of similarity of objects defined as:
where A and B are sets of objects. Jaccard Distance is simply defined as 1 - J_SIM.
"Shingling" in language processing and data mining is extracting set of sub-strings (everyone has length k) from a given string/sequence.
Example. Given a sequence: "Hello, world!", the 3-shingle set is defined as: {"Hel", "ell", "llo", "low", "owo", "wor", "orl", "rld"} (after removing stopwords, blank spaces and punctuation).
The idea of comparing large sets of objects using signatures. A signature is a set (or sequence) representing the main dataset (e.g. a document). The signature has to be a more optimal way of representing large set of objects, than k-shingles method using family of hash functions. One of the method of building signatures is a method of characteristic matrix (but not so efficient if using random permutations). For example, we can consider a signature of the set S, builded from k hash functions:
SIG = (h_1(S), h_2(S), ... , h_k(S))
The most important property, when talking aboout minhash operations is the relation to Jaccard similarity:
The probability that the minhash function for a random permutation of rows produces the same value for two sets equals the Jaccard similarity of those sets.
The approximate Jaccard similarity can be computed using the following formula:
Implement and test HyperLogLog algorithm in two versions according to the original paper (source: http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf).
HyperLogLog (HLL) algorithm is an example of probabilistic algorithm used to approximate the number of distinct elements in multiset.