Information Retrieval and Map-Reduce Implementations Adopted from Jimmy Lin’s slides, which is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 United States Roadmap  Introduction to information retrieval  Basics of indexing and retrieval  Inverted indexing in MapReduce  Retrieval at scale First, nomenclature…  Information retrieval (IR) Focus on textual information (= text/document retrieval) ⚫ Other possibilities include image, video, music, … ⚫  What do we search? Generically, “collections” ⚫ Less-frequently used, “corpora” ⚫  What do we find? Generically, “documents” ⚫ Even though we may be referring to web pages, PDFs, PowerPoint slides, paragraphs, etc. ⚫ Information Retrieval Cycle Source Selection Resource Query Formulation Query Search Results Selection System discovery Vocabulary discovery Concept discovery Document discovery source reselection Documents Examination Information Delivery The Central Problem in Search Searcher Author Concepts Concepts Query Terms Document Terms “tragic love story” “fateful star-crossed romance” Do these represent the same concepts? Abstract IR Architecture Query Documents online offline Representation Function Representation Function Query Representation Document Representation Comparison Function Index Hits How do we represent text?  Remember: computers don’t “understand” anything!  “Bag of words” Treat all the words in a document as index terms ⚫ Assign a “weight” to each term based on “importance” (or, in simplest case, presence/absence of word) ⚫ Disregard order, structure, meaning, etc. of the words ⚫ Simple, yet effective! ⚫  Assumptions Term occurrence is independent ⚫ Document relevance is independent ⚫ “Words” are well-defined ⚫ What’s a word? 天主教教宗若望保祿二世因感冒再度住進醫院。 這是他今年第二度因同樣的病因住院。 ‫ الناطق باسم‬- ‫وقال مارك ريجيف‬ ‫ إن شارون قبل‬- ‫الخارجية اإلسرائيلية‬ ‫الدعوة وسيقوم للمرة األولى بزيارة‬ ‫ التي كانت لفترة طويلة المقر‬،‫تونس‬ 198