An Approach for Improving Execution Performance in

AnApproachforImprovingExecutionPerformanceinInferenceNetworkBasedInformationRetrievalEricW.BrownTechnicalReport94–73September1994DepartmentofComputerScienceUniversityofMassachusettsAmherst,MA01003USAAbstractTheinferencenetworkretrievalmodelprovidestheabilitytocombineavarietyofretrievalstrategiesexpressedinarichquerylanguage.Whilethispoweryieldsimpressiveretrievaleffectiveness,italsopresentsbarrierstotheincorporationoftraditionaloptimizationtechniquesintendedtoimprovetheexecutionefficiency,orspeed,ofretrieval.Theessenceoftheseoptimizationtechniquesistheabilitytoidentifytheindexinginformationthatwillbemostusefulforevaluatingaquery,combinedwiththeabilitytoaccessfromdiskjustthatinformation.Isurveyavarietyoftechniquesintendedtoidentifyusefulindexinginformationandproposeanewstrategyforincorporatingthesetechniquesintotheinferencenetworkretrievalmodel.Additionally,Idescribeanarchitecturebasedonapersistentobjectstorethatprovidessophisticatedmanagementoftheindexingdata,allowingjustthedesiredindexingdatatobeaccessedfromdiskduringretrieval.ThisworkissupportedbytheNationalScienceFoundationCenterforIntelligentInformationRetrievalattheUniversityofMassachusetts.Email:[e-mail].1IntroductionThehumanracehasalonghistoryofputtingthingsinwriting.Inoureffortstocommunicate,record,anddocument,weinevitablygeneratesomewrittenpieceofworkthatcontainshistory,facts,plans,orinformationingeneral.Whilegeneratingtheseworks,whichIshallcalldocuments,isrelativelyeasy,makinguseoftheinformationcontainedinthosedocumentscanbequitedifficult,particularlyiftherearemanydocumentsinexistenceandweareinterestedinonlyafew.Itisexactlythisfunctionality,however,thatismostcritical.Theattorneymustbeabletoidentifypastcasesrelevanttothecurrentcase.Thescientistmustbeabletoidentifytechnicalpapersrelatedtotheirresearch.Theaccountantmustbeabletolocateapplicabletaxlaws.Thecontractormustbeabletofindstandardsandspecificationsrelatedtotheproject.Anyoneinterestedinacurrenteventmustbeabletofindrelevantnewsarticles.Awealthofdocumentsisuselessifwecannotidentifytheonesthatcontaintheinformationweneed.Oneofthefirstsolutionstothisproblemappearednearlyfourthousandyearsagowhencataloguesofdocumentsinlibrarieswerecreatedtoaidinkeepingtrackofthosedocuments.Morerecently,inthe16thcentury,primitiveindexesfordocumentswerecreated.Anindexisalistofcertainkeywordsortopics.Eachentryinthelistcontainspointersintothedocumentswheredescriptionsanddiscussionsoftherespectivekeywordortopicmaybefound.Decidingwhatkeywordsandtopicsshouldgointoanindexandwhichdiscussionsareworthyofanindexpointerisatediousandsubjectivehumantaskpronetoomissions.Ashortcomingofanindexorcatalogueisthataninformationsearchmustbebasedoneitherthekeywordsactuallyindexedortheattributesusedinthecatalogue(e.g.,author,title,subject).Toaddressthislimitation,concordanceswerecreated.Aconcordanceforacollectionofdocumentscontainsanentryforeverytermthatappearsinthecollection.Aterm’sentrycontainsapointertoeveryoccurrenceofthatterm.Now,aninformationsearchwasnolongerrestrictedbypredeterminedkeywordsorattributes.However,aconcordanceforalargedocumentsuchastheBiblemightrequireagoodportionofalifetimetoconstructbyhand,andinonecase,theeffortinvolvedinsuchataskisbelievedtohaveleadtotheinsanityoftheconcordancecompiler[58].Withtheadventofthecomputerageinthelatterhalfofthe20thcentury,concordanceconstructioncouldbeautomated,greatlysimplifyingthetask.Whatusedtotakeyearscouldnowbeaccomplishedinminutes.Inspiteofbeingrelativelycompleteandsimpletoconstruct,aconcordancestillprovidedaratherunsophisticatedsolutiontoouroriginalproblem.Tryingtolocateinformationinalargecollectionofdocumentsusingaconcordancecanbeanexerciseinfrustration,leadingtotheretrievalofmanyunrelateddocumentsthatjusthappentocontaintermsthatwebelieveareindicativeoftheinformationweseek.Amoreintelligentsolutiontotheproblemathandwasstillneeded.Overthirtyyearsago,worktowardsthisintelligentsolutionbeganwiththebirthofinformationretrievalsystems.Thetaskofaninformationretrieval(IR)systemistosatisfyauser’sinformationneedbyidentifyingthedocumentsinacollectionofdocumentsthatcontainthedesiredinformation.Thistaskisaccomplishedthroughtheuseofthreebasiccomponents:adocumentrepresentation,aqueryrepresentation,andameasureofsimilaritybetweenqueriesanddocuments.Thedocumentrepresentationprovidesaformaldescriptionoftheinformationcontainedinthedocuments,thequeryrepresentationprovidesaformaldescriptionoftheinformationneed,andthesimilaritymeasuredefinestherulesandproceduresformatchingtheinformationneedwiththedocumentsthatsatisfythatneed.MuchoftheresearchtodateinIRsystemshasfocussedonhowtoimplementthesethreecomponentsforbestperformance.IntheIRcommunity,“performance”isunderstoodtomeanretrievaleffectiveness,ratherthanexecutionefficiency.RetrievaleffectivenessreferstoanIRsystem’sabilitytocorrectlyidentifythedocumentsthatarerelevanttoagivenquery,andismeasuredintermsofrecallandprecision.Recallisthepercentageoftherelevantdocumentsactuallyidentifiedbythesystem,andprecisionisthepercentageofthedocumentsidentifiedthatarerelevant.F