Scaling personalized web search

[e-mail]@db.stanford.eduStanfordUniversityAbstractRecentwebsearchtechniquesaugmenttraditionaltextmatchingwithaglobalnotionof“importance”basedonthelinkagestructureoftheweb,suchasinGoogle’sPageRankalgorithm.Formorere-finedsearches,thisglobalnotionofimportancecanbespecializedtocreatepersonalizedviewsofimportance—forexample,importancescorescanbebiasedaccordingtoauser-specifiedsetofinitially-interestingpages.Computingandstoringallpossi-blepersonalizedviewsinadvanceisimpractical,asiscomputingpersonalizedviewsatquerytime,sincethecomputationofeachviewrequiresaniterativecomputationoverthewebgraph.Wepresentnewgraph-theoreticalresults,andanewtechniquebasedontheseresults,thatencodepersonalizedviewsaspartialvectors.Partialvectorsaresharedacrossmul-tiplepersonalizedviews,andtheircomputationandstoragecostsscalewellwiththenumberofviews.Ourapproachenablesincrementalcomputation,sothattheconstructionofpersonalizedviewsfrompar-tialvectorsispracticalatquerytime.Wepresentefficientdynamicprogrammingalgorithmsforcom-putingpartialvectors,analgorithmforconstructingpersonalizedviewsfrompartialvectors,andexper-imentalresultsdemonstratingtheeffectivenessandscalabilityofourtechniques.1IntroductionandMotivationGeneralwebsearchisperformedpredominantlythroughtextqueriestosearchengines.Becauseoftheenormoussizeoftheweb,textaloneisusuallynotselectiveenoughtolimitthenumberofqueryresultstoamanageablesize.ThePageRankalgorithm[10],amongothers[8],hasbeenproposed(andimplementedinGoogle[1])toexploitthelinkagestructureofthewebtocomputeglobal“importance”scoresthatcanbeusedtoinfluencetherankingofsearchresults.Toencompassdifferentnotionsofimportancefordifferentusersandqueries,thebasicPageRankalgorithmcanbemodifiedtocreate“person-alizedviews”oftheweb,redefiningimportanceaccord-ingtouserpreference.Forexample,ausermaywishtospecifyhisbookmarksasasetofpreferredpages,sothatThisworkwassupportedbytheNationalScienceFoundationundergrantIIS-9817799.anyqueryresultsthatareimportantwithrespecttohisbookmarkedpageswouldberankedhigher.Whileex-perimentationwiththeuseofpersonalizedPageRankhasshownitsutilityandpromise[5,10],thesizeofthewebmakesitspracticalrealizationextremelydifficult.Toseewhy,letusreviewtheintuitionbehindthePageRankal-gorithmanditsextensionforpersonalization.ThefundamentalmotivationunderlyingPageRankistherecursivenotionthatimportantpagesarethoselinked-tobymanyimportantpages.Apagewithonlytwoin-links,forexample,mayseemunlikelytobeanimportantpage,butitmaybeimportantifthetworef-erencingpagesareYahoo!andNetscape,whichthem-selvesareimportantpagesbecausetheyhavenumerousin-links.Onewaytoformalizethisrecursivenotionistousethe“randomsurfer”modelintroducedin[10].Imag-inethattrillionsofrandomsurfersarebrowsingtheweb:ifatacertaintimestepasurferislookingatpagep,atthenexttimestephelooksatarandomout-neighborofp.Astimegoeson,theexpectedpercentageofsurfersateachpagepconverges(undercertainconditions)toalimitr(p)thatisindependentofthedistributionofstart-ingpoints.Intuitively,thislimitisthePageRankofp,andistakentobeanimportancescoreforp,sinceitre-flectsthenumberofpeopleexpectedtobelookingatpatanyonetime.ThePageRankscorer(p)reflectsa“democratic”im-portancethathasnopreferenceforanyparticularpages.Inreality,ausermayhaveasetPofpreferredpages(suchashisbookmarks)whichheismorelikelytolookat,oratleasttostartbrowsingfromeachday.Wecanaccountforpreferredpagesintherandomsurfermodelbyintroducinga“teleportation”probability:ateachstep,asurferjumpsbacktoarandompageinPwithprobability,andwithprobability1continuesforthalongahyperlink.ThelimitdistributionofsurfersinthismodelwouldfavorpagesinP,pageslinked-tobyP,pageslinked-tointurn,etc.Werepresentthisdistri-butionasapersonalizedPageRankvector(PPV)person-alizedonthesetP.Informally,aPPVisapersonalizedviewoftheimportanceofpagesontheweb.Rankingsofauser’stext-basedqueryresultscanbebiasedaccordingtoaPPVinsteadoftheglobalimportancedistribution.EachPPVisoflengthn,wherenisthenumberof1pagesontheweb.ComputingaPPVnaivelyusingafixed-pointiterationrequiresmultiplescansofthewebgraph[10],whichmakesitimpossibletocarryoutonlineinresponsetoauserquery.Ontheotherhand,PPV’sforallpreferencesets,ofwhichthereare2n,isfartoolargetocomputeandstoreoffline.WepresentamethodforencodingPPV’saspartially-computed,sharedvectorsthatarepracticaltocomputeandstoreoffline,andfromwhichPPV’scanbecomputedquicklyatquerytime.InourapproachwerestrictpreferencesetsPtosub-setsofasetofhubpagesH,selectedasthosemoreim-portantforpersonalization.Inpractice,weexpectHtobeasetofpageswithhighPageRank(“importantpages”),pagesinahuman-constructeddirectorysuchasYahoo!orOpenDirectory[2],orpagesimportanttoaparticularenterpriseorapplication.ThesizeofHcanbethoughtofastheavailabledegreeofpersonaliza-tion.Wepresentalgorithmsthat,unlikepreviouswork[5,10],scalewellwiththesizeofH.Moreover,thesametechniquesweintroducecanyieldapproximationsonthemuchbroadersetofallPPV’s,allowingatleastsomelevelofpersonalizationonarbitrarypreferencesets.Themaincontributionsofthispa