'''Originally Posted By: sushma'''

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