Yioop - PHP Search Engine

2012-12-12

Practice final solution for Problem 7.

Originally Posted By: sushma

BM25 Formula :
BM25.png
From the above BM25 formula, the components like N, Nt, ld, lavg,f(t,d) need to be precomputed before query time.
lavg, N and Nt are the components which would benefit from being calculated using map reduce algorithm.

Map Reduce implementation to calculate Average Document Length :
The average document length is the total number of tokens divided by the total number of documents.

Let our initial key value pairs be (docid, document). The mapper will produce key value pairs of the form ("doc_count", 1) and ("token_count", 1) according to the following (we assume or arrange both keys go to same reducer).
Code: map(docid, document) {
output("doc_count", 1);
for each token t in document {
output ("token_count", 1);
}
return;
}

The reducer then adds these pairs as follows:
Code: reduce(key, (v[1],... v[n])) { // remark v[i] will always be 1
static total_docs = 0;
static total_tokens = 0;
for i = 1 to n {
if(key == "doc_count") {
total_docs += v[i];
}
if(key == "token_count") {
total_tokens += v[i];
}
}
if(total_docs > 0) {
return total_tokens/total_docs;
}
return -1;
}
We assume if we see -1, we should wait for the second return value of the function

Group Members : Jiten Oswal, Sushma Bandekar, Geetha Ranjini Viswanathan

'''Originally Posted By: sushma''' BM25 Formula : BM25.png From the above BM25 formula, the components like N, Nt, ld, lavg,f(t,d) need to be precomputed before query time. lavg, N and Nt are the components which would benefit from being calculated using map reduce algorithm. Map Reduce implementation to calculate Average Document Length : The average document length is the total number of tokens divided by the total number of documents. Let our initial key value pairs be (docid, document). The mapper will produce key value pairs of the form ("doc_count", 1) and ("token_count", 1) according to the following (we assume or arrange both keys go to same reducer). Code: map(docid, document) {   output("doc_count", 1);   for each token t in document {      output ("token_count", 1);   }   return; } The reducer then adds these pairs as follows: Code: reduce(key, (v[1],... v[n])) { // remark v[i] will always be 1     static total_docs = 0;     static total_tokens = 0;     for i = 1 to n {         if(key == "doc_count") {             total_docs += v[i];         }         if(key == "token_count") {             total_tokens += v[i];         }     }     if(total_docs > 0) {        return total_tokens/total_docs;     }     return -1; } We assume if we see -1, we should wait for the second return value of the function Group Members : Jiten Oswal, Sushma Bandekar, Geetha Ranjini Viswanathan