1Elementary IRSystems: SupportingBoolean Text SearchInformation Retrieval• A research field traditionally separate from Databases– Goes back to IBM, Rand and Lockheed in the 50’s– G. Salton at Cornell in the 60’s– Lots of research since then• Products traditionally separate– Originally, document management systems for libraries,government, law, etc.– Gained prominence in recent years due to web search• Today: simple IR techniques– Show similarities to DBMS techniques you already know– We’ll skip:• Specialized storage tricks• Ranking results (hopefully later!)• Parallelism (hopefully later)• Bells and whistles (lots of little ones!)IR vs. DBMS• Seem like very different beasts• Under the hood, not as different as they might seem– But in practice, you have to choose between the 2Expect reasonable number ofupdatesRead-Mostly. Add docsoccasionallySQLKeyword searchGenerate full answerPage through top k resultsStructured dataUnstructured data formatPrecise SemanticsImprecise SemanticsDBMSIRIR’s “Bag of Words” Model• Typical IR data model:– Each document is just a bag of words (“terms”)• Detail 1: “Stop Words”– Certain words are considered irrelevant and not placed inthe bag– e.g. “the”– e.g. HTML tags like <H1>• Detail 2: “Stemming”– Using English-specific rules, convert words to their basicform– e.g. “surfing”, “surfed” --> “surf”– Unfortunately have to do this for each language• Yuck!Boolean Text Search• Find all documents that match a Booleancontainment expression:– “Windows” AND (“Glass” OR “Door”) AND NOT “Microsoft”• Note: query terms are also filtered viastemming and stop words• When web search engines say “10,000documents found”, that’s the Boolean searchresult size.Text “Indexes”• When IR folks say “text index”…– !usually mean more than what DB people mean• In our terms, both “tables” and indexes– Really a logical schema (i.e. tables)– With a physical schema (i.e. indexes)– Usually not stored in a DBMS• Tables implemented as files in a file system• We’ll talk more about this decision soon2A Simple Relational Text Index• Create and populate a tableInvertedFile(term string, docURL string)• Build a B+-tree or Hash index on InvertedFile.term– Something like “Alternative 3” critical here!!• Keep lists of dup keys sorted by docURL• Fancy list compression important, too• Typically called a “postings list”– Note: URL instead of RID, the web is your “heap file”!• Can also cache pages and use RIDs• This is often called an “inverted file” or “inverted index”– Maps from words -> docs• whereas normal files map docs to the words in the doc!• Can now do single-word text search queries!An Inverted File• Snippets from:– Class web page– microsoft.com• Search for– databases– microsoftterm docURLdata http://www-inst.eecs.berkeley.edu/~cs186database http://www-inst.eecs.berkeley.edu/~cs186date http://www-inst.eecs.berkeley.edu/~cs186day http://www-inst.eecs.berkeley.edu/~cs186dbms http://www-inst.eecs.berkeley.edu/~cs186decision http://www-inst.eecs.berkeley.edu/~cs186demonstrate http://www-inst.eecs.berkeley.edu/~cs186description http://www-inst.eecs.berkeley.edu/~cs186design http://www-inst.eecs.berkeley.edu/~cs186desire http://www-inst.eecs.berkeley.edu/~cs186developer http://www.microsoft.comdiffer http://www-inst.eecs.berkeley.edu/~cs186disability http://www.microsoft.comdiscussion http://www-inst.eecs.berkeley.edu/~cs186division http://www-inst.eecs.berkeley.edu/~cs186do http://www-inst.eecs.berkeley.edu/~cs186document http://www-inst.eecs.berkeley.edu/~cs186document http://www.microsoft.commicrosoft http://www.microsoft.commicrosoft http://www-inst.eecs.berkeley.edu/~cs186midnight http://www-inst.eecs.berkeley.edu/~cs186midterm http://www-inst.eecs.berkeley.edu/~cs186minibase http://www-inst.eecs.berkeley.edu/~cs186million http://www.microsoft.commonday http://www.microsoft.commore http://www.microsoft.commost http://www-inst.eecs.berkeley.edu/~cs186ms http://www-inst.eecs.berkeley.edu/~cs186msn http://www.microsoft.commust http://www-inst.eecs.berkeley.edu/~cs186necessary http://www-inst.eecs.berkeley.edu/~cs186need http://www-inst.eecs.berkeley.edu/~cs186network http://www.microsoft.comnew http://www-inst.eecs.berkeley.edu/~cs186new http://www.microsoft.comnews http://www.microsoft.comnewsgroup http://www-inst.eecs.berkeley.edu/~cs186Handling Boolean Logic• How to do “term1” OR “term2”?– Union of two DocURL sets!• How to do “term1” AND “term2”?– Intersection of two postings lists!• Can be done via merge-join over postings lists• Remember: postings list per key sorted by DocURL in index• How to do “term1” AND NOT “term2”?– Set subtraction• Also easy because sorted• How to do “term1” OR NOT “term2”– Union of “term1” and “NOT term2”.• “Not term2” = all docs not containing term2. Yuck!– Usually not allowed!• Query Optimization: what order to handle terms if youhave many ANDs?Boolean Search in SQL• (SELECT docURL FROM InvertedFile WHERE word = “window” INTERSECT SELECT docURL FROM InvertedFile WHERE word = “glass” OR word = “door”)EXCEPTSELECT docURL FROM InvertedFile WHERE word=“Microsoft”ORDER BY magic_rank()• Really only one SQL query template in Boolean Search– Single-table selects, UNION, INTERSECT, EXCEPT• magic_rank() is the “secret sauce” in the search engines– Hopefully we’ll study this later in the semester– Combos of statistics, linguistics, and graph theory tricks!“Windows” AND (“Glass” OR “Door”) AND NOT “Microsoft”Fancier: Phrases and “Near”• Suppose you want a phrase– E.g. “Happy Days”• Different schema:– InvertedFile (term string, count int, position int, DocURLstring)– Alternative 3 index on term– Postings lists sorted by (DocURL, position)• Post-process the results– Find “Happy” AND “Days”– Keep results where positions are 1 off• Can be done during merge-join to AND the 2 lists!• Can do a similar thing for “term1” NEAR “term2”– Position < k off– Think about refinement to merge-join…Somewhat better compression– InvertedFile (term string, count int, position int,docID int)– Docs(docID int, docURL string, snippet string, …)– Btree on InvertedFile.term– Btree on Docs.docID–
View Full Document
Unlocking...