文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > Performance Evaluation of Inverted Index Traversal Techniques
侵权投诉

Performance Evaluation of Inverted Index Traversal Techniques

PerformanceEvaluationofInvertedIndexTraversal

Techniques

KunJiang,XingshenSong,YuexiangYang

CollegeofComputer

NationalUniversityofDefenseTechnology

Changsha,China

{jiangkun,songshengshen14,yyx}@nudt.edu.cn

Abstract—Largesearchenginesprocessthousandsofqueriespersecondoverbillionsofdocuments,makingqueryprocessingamajorperformancebottleneck.Inthispaper,westudyanimportantclassofindextraversaltechniquescalleddynamicpruning,whichcanef cientlyreducethequerycomputationalresources.Wegivebriefoverviewsofindexstructureandskippingstructurethatusedtoquickentheterm-centricanddocument-centricindextraversalstrategies.Duetothefactthatdocument-centricismoreef cientthanterm-centricforlargeindexes,wereviewseveralstate-of-the-artdynamicpruningapproachesbasedondocument-centricscoring.WethenpresentexplicitexperimentalcomparisonsoftheaboveindextraversaltechniquesonTRECGOV2datasetswithdetailedanalyticalconclusions.Finally,weprovidetheprospectivefuturestudyofdynamicpruningwithlargescaleofindexes.

Keywords—performanceevaluation;invertedindex;indextraversal;dynamicpruning

ndthesuperiorofDAAToverTAATwithlargerindexesandalsotheperformancegapbetweendisjunctiveandconjunctivequeries.Inordertoreducethishugeperformancegap,wemakeanin-depthdescriptionoftwostate-of-the-artdynamicpruningtechniques,i.e.,MaxScoreandWAND(Weak-AND),andpresentdetailedcomparisonsofthetechniquesbasedonDAATindextraversal.

Therestofthispaperisstructuredasfollows:Section2brie yreviewsbasicconceptsoninvertedindexstructureandskippingstructure.Section3analyzesthebasicterm-centricanddocument-centricindextraversalanddescribesseveralstate-of-artdynamicpruningstrategies.Section4detailstheexperimentalsettingsandcomparisonresults.Finally,Section5concludesthispaperandpresentsaprospectiveoffuturework.

II.

A.InvertedIndex

Theinvertedindexplaysavitalroleintheef cientpro-cessingofrankedandbooleanqueries[6].GivenacollectionofNdocuments,weassumethateachdocumentisidenti edbyauniquedocumentidenti er(docid)between0andN-1.Aninvertedindexcanbeseenasanarrayoflistsorpostings,whereeachentryofthearraycorrespondstoadifferenttermorwordinthecollection.Foreachtermt,theindexcontainsaninvertedlistItconsistingofanumberofindexpostingsdescribingallplaceswheretermtoccursinthecollection.Moreprecisely,eachpostinginItcontainsthedocidandthenumberofoccurrencesofwinthedocument(calledfrequency),andpossiblyotherinformationaboutthelocationsoftheoccurrenceswithinthedocumentandtheircontexts.Thepostingsineachlistareusuallysortedbydocid.Fig.1isanexampleofinvertedindexstructure,showingthephysicalstorageoflexiconandpostinglists.Weassumepostingshavedocidsandfrequenciesbutdonotconsiderotherdatasuchaspositionsorcontexts,thuseachpostingisoftheform(di,fi).Thesetoftermsiscalledthelexiconofthecollection,whichiscomparativelysmallinmostcases.However,theinvertedlistsmayconsistofmanymillionsofpostingswhichcouldberoughlylinearwiththesizeofthecollection.Toallowfasteraccessandlimittheamountofmemoryneeded,searchenginesusevariouscompressiontechniquesthatsigni cantlyreducethesizeoftheinvertedlists.Compressioniscrucialforsearchengineperformanceandmanycompressiontechniqueshavebeenproposedbyresearchers,see[8],[9]forsomerecent

BASICCONCEPTS

I.INTRODUCTION

DuetotherapidgrowthoftheInternet,moreandmorepeo-plearerelyingonsearchenginestolocateusefulinformation.Largescalesearchenginesprocessthousandsofqueriespersecondoverbillionsofdocuments,makingqueryprocessingamajorperformancebottleneck[1].OnemajorprobleminqueryprocessingisthatthelengthoftheinvertedlistcaneasilygrowtohundredsofMBsorevenGBsforcommonterms.Giventhatsearchenginesneedtoanswerquerieswithinfractionsofasecond,naivelytraversingthebasicindexstructure,whichcouldtakehundredsofmilliseconds,isnotacceptable.Thisbasicproblemhaslongbeenrecognizedbyresearchers,andhasmotivatedalotofworkonoptimizationtechniquesincludinginvertedindexpartitioning,distribution,indexcompressionandindextraversaloptimization[2],[3],[4],[5].

Inthispaper,wereviewtheindexstructureandindextraversaltechniques[6],[7],includingthefullexhaustivetraversalanddynamicpruningtraversal(alsocalledtop-kpro-cessing),whichinanutshellmeansreturningthebestkresultswithoutanexhaustivetraversaloftherelevantpostinglists.Broadly,theexhaustiveindextraversaltechniquesfallintotwocategories:document-centricscoringandterm-centricscoring,knownasDocument-At-A-Time(DAAT)andTerm-At-A-Time(TAAT).WeimplementalltheindextraversaltechniquesandpresentdetailedexperimentalcomparisonsbasedonTRECGOV2documentcollection.Moreprecisely,we rstlyperformdirectexperimentalcomparisonsofDAATandTAATwithtwoboolean lters,i.e.,disjunctiveandconjunctivequeries,and

第1页

你可能喜欢

热门文档

相关文档

  • Performance Evaluation

    Performance Evaluation_生产/经营管理_经管营销_专业资料 暂无评价0人阅读0次下载举报文档 Performance Evaluation_生产/经营管理_经管营销_专业资料。Performance ...

  • Effective Performance Appraisals

    Effective Performance Appraisals By Natalie Dee A company's performance depends to a great extent on effective performance appraisal of its workforce. An ...

  • Corporate Performance

    Corporate Performance_英语学习_外语学习_教育专区。Corporate Performance3Q 2008 Corporate Performance Oct. 29, 2008 Disclaimer This presentation contains forward-...

  • Performance Appraisal

    PERFORMANCE APPRAISAL 受评者/Employee 受评者 年龄/Age 年龄 职位/Position 职位 评估者/Appraiser 评估者 部门/Dept. 部门 日期/Date 日期 A 行为准则 2010 ...

  • Routing Performance

    Last updated November 3, 2009 Portable Product Sheets – Routing Performance Router Switching Performance in Packets Per Second (PPS) Numbers are given ...

  • performance measurement(1)

    A ORIGINAL ARTICLE 1 performance measurement 7 Blackwell Journal of Ltd 2005 paradigm March 2005 Publishers Management Reviews for integrating strategy ...

  • Performance indicator【Wikipedia】

    Performance indicator【Wikipedia】_企业管理_经管营销_专业资料 暂无评价0人阅读0次下载举报文档 Performance indicator【Wikipedia】_企业管理_经管营销_专业资料。...

  • 公司的 performance measurement

    performance measurement(... 24页 免费 Performance measurement 36页 5财富值 Performance Measurement 暂无评价 4页 1财富值 Performance Measurement... 暂无评价...

  • ADMINISTRATOR PERFORMANCE APPRAISAL.doc

    ADMINISTRATOR PERFORMANCE APPRAISAL SELF EVALUATION EMPLOYEE DATA Employee: Department: Supervisor: Job Title: Appraisal Date: From Date of Hire: To I. GOALS...

  • performance appraisal

    performance appraisal_高等教育_教育专区。培训讲师简介 黄维德 上海经济发展研究所 人力资源管理教授 Tel: 64253210(O) , 64248141(H) E-Mail: huangwd222@163...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email