Slide 1Presentation OverviewProblemSolution = Search EngineSpecific Design GoalsGoogle Search Engine FeaturesPageRank For LaymanPageRank For TechiesWhy do we need d?Justifications for using PageRankGoogle ArchitecturePreliminaryGoogle Architecture (cont.)Google Architecture (cont.)Slide 15Google Query EvaluationSingle Word Query RankingMulti-word Query RankingScalabilitySummary of Key Optimization TechniquesReferences:Presented By:Vamsee Raja Jarugula for the sake of CIS 764 presentation . Kansas State University.Presentation OverviewProblem Definition.Design GoalsGoogle Search Engine Characteristics.Google ArchitectureScalability Conclusions Vamsee Raja Jarugula CIS 764ProblemWeb is vast and ever expanding. It is getting flooded with data.This data is heterogeneous and consists of all forms TextImagesAsciiJava applets Lists maintained by Humans cannot keep track of this.Human attention is confined to 10-1000 documentsPrevious search methodologies relied on keyword matching producing inferior quality results. Vamsee Raja Jarugula CIS 764Solution = Search Engine•Search engines facilitate users to get the text or documents of their choice within a click of mouse. ”Some examples of Search engines:Google,Altavista,MetaCrawler,Kosmix.For comprehensive list of search engines do visit:http://en.wikipedia.org/wiki/List_of_search_engines Vamsee Raja Jarugula CIS 764Specific Design GoalsDeliver results that have very high precision even at the expense of recallBring search engine technology into academic realm in order to support novel research activities Make search engine technology transparent, i.e. advertising shouldn’t bias resultsMake system user friendly . Vamsee Raja Jarugula CIS 764Google Search Engine FeaturesUses link structure of web (PageRank)Uses text surrounding hyperlinks to improve accurate document retrievalOther features include:Takes into account word proximity in documentsUses font size, word position, etc. to weight wordStorage of full raw html pages Vamsee Raja Jarugula CIS 764PageRank For LaymanImagine a web surfer doing a simple random walk on the entire web for an infinite number of steps. Occasionally, the surfer will get bored and instead of following a link pointing outward from the current page will jump to another random page.At some point, the percentage of time spent at each page will converge to a fixed value. This value is known as the PageRank of the page. Vamsee Raja Jarugula CIS 764PageRank For TechiesN(p): # outgoing links from page pB(p): set of pages that point to pd: tendency to get “bored” .R(p): PageRank of pR(p) = [(1-d)+d*R(q)/N(q)] . Vamsee Raja Jarugula CIS 764Why do we need d?In the real world virtually all web graphs are not connected, i.e. they have dead-ends, islands, etc.If we don’t have d we get “ranks leaks”for graphs that are not connected, i.e. leads to numerical instability. Vamsee Raja Jarugula CIS 764Justifications for using PageRankAttempts to model user behaviorCaptures the notion that the more a page is pointed to by “important” pages, the more it is worth looking atTakes into account global structure of web Vamsee Raja Jarugula CIS 764Google ArchitectureImplemented in C and C++ on Solaris and Implemented in C and C++ on Solaris and LinuxLinux Reference from Anatomy of a large scale search engine –Sergy Brin, Larry Page.Preliminary“Hitlist” is defined as list of occurrences of a particular word in a particular document including additional meta info:- position of word in doc - font size - capitalization - descriptor type, e.g. title, anchor, etc. Vamsee Raja Jarugula CIS 764Google Architecture (cont.)core figure referred from Sery Brin and Larry Page.----Anatomy of a large scale search engine.Google Architecture (cont.)Core figure referred from Sergy Brin and Larry Page.Google Architecture (cont.)Core figure reference from Sergy Brin and Larry page.Google Query Evaluation1.1.Parse the query. Parse the query. 2.2.Convert words into wordIDs. Convert words into wordIDs. 3.3.Seek to the start of the doclist in the short barrel Seek to the start of the doclist in the short barrel for every word. for every word. 4.4.Scan through the doclists until there is a Scan through the doclists until there is a document that matches all the search terms. document that matches all the search terms. 5.5.Compute the rank of that document for the query. Compute the rank of that document for the query. 6.6.If we are in the short barrels and at the end of any If we are in the short barrels and at the end of any doclist, seek to the start of the doclist in the full doclist, seek to the start of the doclist in the full barrel for every word and go to step 4. barrel for every word and go to step 4. 7.7.If we are not at the end of any doclist go to step If we are not at the end of any doclist go to step 4.4.8.8.Sort the documents that have matched by rank Sort the documents that have matched by rank and return the top k.and return the top k. Vamsee Raja Jarugula CIS 764Single Word Query RankingHitlist is retrieved for single wordEach hit can be one of several types: title, anchor, URL, large font, small font, etc.Each hit type is assigned its own weightType-weights make up vector of weights# of hits of each type is counted to form count vectorDot product of two vectors is used to compute IR scoreIR score is combined with PageRank to compute final rank Vamsee Raja Jarugula CIS 764Multi-word Query RankingSimilar to single-word ranking except now must analyze proximityHits occurring closer together are weighted higherEach proximity relation is classified into 1 of 10 values ranging from a phrase match to “not even close”Counts are computed for every type of hit and proximity Vamsee Raja Jarugula CIS 764ScalabilityCluster architecture combined with Moore’s Law make for high scalability. At time of writing:~ 24 million documents indexed in one week~518 million hyperlinks indexedFour crawlers collected 100 documents/sec Vamsee Raja Jarugula CIS 764Summary of Key Optimization TechniquesEach crawler maintains its own DNS lookup cacheUse flex to generate lexical analyzer with own stack for parsing documentsParallelization of indexing phaseIn-memory lexiconCompression of repositoryCompact encoding of
View Full Document
Unlocking...