N-Gram AutoComplete
N-Gram Library
Build N-Gram Library from input text file
The first step is parsing the input text file and passing it to the Map Reduce job. The mapper would split the words on distributed nodes and the reducer would sum up each word for 2 to N-1 gram.
Language Model
Build Language Model on local DatabaseTaking the intermedium key-value pair from the first Map Reduce job, copying them to the local database (mySql). Try another Map Reduce job to rank the top K possible words for N-Gram auto complete
Fig 1. Auto complete demo
Fig 2. Table in mySql
Google PageRank
Transition Matrix & PageRank Vector
Initializing the Transition Matrix and the Page Rank Vector
Two assumptions:
(1) More important websites are likely to receive more links from others;
(2) Websites with higher Page Rank will pass higher weight.
parallel matrix multiplication
Implementing matrix multiplication with Map Reduce
Matrix size: 6012 × 6012;
Vector size: 6012 × 1
Two Map Reduce jobs are required. First MR job deals with Matrix row × PR cell; second MR job sums up cell for each page to get their ranks.
Fig 1. left: Rank index before iteration; right: Rank index after iteration
Recommender System
Collaborative Filtering (Item)
Generating relevancy matrix via Item CF
Build co-occurrence matrix based on users' rating history
Build user-specific rating vector from his/her rating history
Matrix computation to find out the recommending result
processing with with Map Reduce
Implementing data processing & matrix multiplication
Pre-processing for generating the co-occurrence matrix with 2-Gram method;
Matrix computation using Pagerank method with only iterating once and teleporting index to be 0.
Fig 1.Demo of recommender system left: User's rating; right: Recommender ranks
Reference
[1] J. Dean and S. Ghemawat. MapReduce: Simplified Data Processing on Large Clusters.
[2] http://searchengineland.com/what-is-google-pagerank-a-guide-for-searchers-webmasters-11068