We propose a new ranking paradigm for relational databases called Structured Value Ranking (SVR). SVR uses structured data values to score (rank) the results of keyword search queries over text columns. Our main contribution is a new family of inverted lis
Ef cientInvertedListsandQueryAlgorithmsforStructuredValueRanking
inUpdate–IntensiveRelationalDatabases
LinGuo
JayavelShanmugasundaram
CornellUniversityguolin,jai@cs.cornell.edu
Abstract
WeproposeanewrankingparadigmforrelationaldatabasescalledStructuredValueRanking(SVR).SVRusesstructureddatavaluestoscore(rank)theresultsofkey-wordsearchqueriesovertextcolumns.Ourmaincontri-butionisanewfamilyofinvertedlistindicesandassoci-atedqueryalgorithmsthatcansupportSVRef cientlyinupdate–intensivedatabases,wherethestructureddataval-ues(andhencethescoresofdocuments)changefrequently.Ourexperimentalresultsonrealandsyntheticdatasetsus-ingBerkeleyDBshowthatwecansupportSVRef cientlyinrelationaldatabases.
1Introduction
SQL/MM[23]isthestandardextensiontoSQLforpro-cessingtextdata.Currentrelationaldatabasesthatimple-mentSQL/MM[9,10]treatthetextmanagementcompo-nentasa“blackbox”andusetraditionalrankingtechniquessuchasTF–IDF[26].Suchrankingtechniques,however,wereoriginallydevelopedbytheIRcommunityforstand–alonedocumentcollectionsandoftendonotproducemean-ingfulresultsfortextstoredinrelationaldatabases.Asanillustration,considertherelationaldatabaseinFigure1,whichcontainsfragmentsofdatafromtheInternetArchive(doc.guandang.net)database,andtheSQL/MMquerybelow,whichreturnsthetop10movieswhosedescriptioncontainsthekeywords“goldengate”.UsingTF–IDF,thetwomoviesinthedatabasewillhaveaboutthesamescoreinthequeryresultbecausethekeywords“goldengate”occurthesamenumberoftimes(i.e.,once)inbothofthemandtheirtext eldlengthsareaboutthesame.Inotherwords,thetwomovieswillhavesimilarscoresdespitethefactthattheyhaveverydifferentpopularitiesbasedontheirreviewratingsandnumberofvisits/downloadsinthedatabase.SELECT*
FROM
Moviesm
ORDERBYscore(m.desc,"goldengate")FETCHTOP
10RESULTSONLY
KevinBeyerEugeneShekita
IBMAlmadenResearchCenterkbeyer,shekita@almaden.ibm.com
Inthispaper,weproposeStructuredValueRanking(SVR),whichusesthestructureddatavaluesrelatedtothetextdatainordertorankkeywordsearchqueryresults.Inourexample,usingSVR,wecanscoreamoviebasedonacombinationofits(a)averagereviewerratings,(b)num-berofvisitsbyusers,and(c)numberofdownloads.Thus,themovie“AmericanThrift”willbeclearlyrankedabove“AmateurFilm”sinceithasreceivedhigherratings,visitsanddownloads.OneofthecontributionsofthispaperisaSQL–basedframeworkforspecifyingandintegratingSVRinarelationaldatabase.Asystemadministratororanau-tomaticrankingtoolcanuseSQLqueriestospecifyhowtextcolumnsaretobescoredbasedonthevaluesofre-latedstructureddata(suchasaveragereviewerratings).OurframeworkalsoenablesrankingbasedonacombinationofSVRandTF–IDF.
ThemaincontributionofthispaperisanewfamilyofinvertedlistindicesandqueryalgorithmsthatcansupportSVRef cientlyinrelationaldatabases.Themainchal-lengeindevisingtheseindicesistoef cientlysupporttop–querieswhenthescoresofthetextcolumnschangefre-quentlyandpossiblydramatically.OurinitialmotivationforthisproblemaroseinthecontextoftheInternetArchivedatabase,wherethereviewerratings,numberofvisitsandnumberofdownloadswereupdatedoftenandsigni cantlychangedthescoresoftheassociatedtextcolumns(fre-quently,thesechangesaredueto“ ashcrowds”ontheInternet,whereanitemsuddenlygainspopularityduetosomeexternaleventsuchasanawardannouncement[2]).Fromtheuser’spointofview,theywouldstillliketoseethetoprankedresultsbasedonthelatestscoressothattheydonotmissimportantrecentinformation.Webelievethatthisisalsotrueforalargeclassofotherupdate–intensivedatabaseswhereSVRisapplicable,suchasstockdatabases(wherevolumeoftradecanbeusedtorankresults),on-lineauctionssuchase–bay(wheretimetocompletionandthecurrentbidcanbeusedtorankresults)andahostofotherweb–basedapplicationswherethepopularityofanitemsometimeschangesdramaticallyinaspanofafew
Efficient inverted lists... 暂无评价 12页 免费 Algorithms for Molecular..... efficient structured pattern and profile motif search Yongqiang Zhang and ...
path expressions over graph/tree-structured XML ...inverted lists and a query evaluation algorithm ...structure indexes and inverted list join algorithms...
Motivation – Structured q query y languages g g...Research Challenges –––– Efficient algorithms ..., – Inverted lists of li, Li – The Th ...
Ranking Page Authority Link Map Inverted Index ...Algorithms Least Square Retrieval Function Query ... a structured SVM approach to listwise ranking (...
The most efficient algorithms for aligning two ... and then build inverted lists for these ...Each group is then structured recursively in the ...
Algorithms Least Square Retrieval Function Query ...ListMLE (ICML 2008) – An efficient variant of ... a structured SVM approach to listwise ranking (...
ranking algorithms such that they can be applied ...exibility. Structured systems, such as those based...An inverted index lists all the objects that ...
supports better ranking algorithms Inverted Index ...query features efficient – e.g., Fields and ...likely to produce good documents Structured Queries...
for result aggregation over the inverted lists. ...was addressed in [2] for the structured topology...Framework for Distributed Top-K Query Algorithms. ...
Unlike traditional inverted index implementations, ...frequent updates and efficient parallel ...C. McCabe. On the integration of structured data...
热门文档