Running Title Searching the Web by Constrained Spr

SearchingtheWebbyConstrainedSpreadingActivationFabioCrestaniPuayLengLeeDepartmentofComputingScienceUniversityofGlasgowGlasgowG128QQ,ScotlandTel.+44-(0)141-3306292Fax.[phone]Email:ffabio,[e-mail]:SearchingtheWebbyConstrainedSpreadingActivation.Keywords(fromACMComputingClassicationSystem):hyper-text/hypermedia,informationsearchandretrieval,spreadingactivation,queryformulation,intelligentagents.1AbstractIntelligentInformationRetrievalisconcernedwiththeapplicationofintelligenttechniques,likeforexamplesemanticnetworks,neuralnetworksandinferencenetstoInformationRetrieval.TheeldofresearchhasseenanumberofapplicationsofConstrainedSpreadingActivation(CSA)techniquesondomainknowledgenetworks.How-ever,therehasneverbeenanyapplicationofthesetechniquestotheWorldWideWeb.TheWebisaveryimportantinformationresource,butusersndthatlookingforarelevantpieceofinformationintheWebcanbelike\lookingforaneedleinahaystack.Wewerethere-foremotivatedtodesignanddevelopaprototypesystem,WebSCSA(WebSearchbyCSA),thatappliesaCSAtechniquetoretrieveinfor-mationfromtheWebusinganostensiveapproachtoqueryingsimilartoquery-by-example.Inthispaperwedescribethesystemanditsun-derlyingmodel.Furthermore,wereportonanexperimentcarriedoutwithhumansubjectstoevaluatetheeectivenessofWebSCSA.WetestedwhetherWebSCSAimprovesretrievalofrelevantinformationontopofWebsearchenginesresultsandhowwellWebSCSAservesasanagentbrowserfortheuser.Theresultsoftheexperimentsarepromising,andshowthatthereismuchpotentialforfurtherresearchontheuseofCSAtechniquestosearchtheWeb.21IntroductionThispaperisconcernedwiththeapplicationofConstrainedSpreadingAc-tivation(CSA)techniquesforretrievinginformationfromtheWorldWideWeb(herebyreferredtoastheWeb).TheWebpresentsaformidablestoreofinformation.Itisaninterconnectedsystemofover7millionsitesandtheirpages(inDecember1998)accessiblethroughbrowserslikeMosaic,NetscapeNavigatororMicrosoft’sInternetExplorer.AlthoughtheWebisoneoftheneweradditionstotheInternet,ithasgainedpopularityveryquickly,be-comingthesecondmostfrequently-usedfeatureoftheInternet,themostwidely-usedonebeingelectronicmail(Berners-Leeetal.,1992).TheinformationstoredintheWebdiersfromtheinformationtraditionallydealtbyInformationRetrieval(IR)systemsinseveralaspects.Informationorganization.TheWebisnotorganized,inthesensethatassociatedorsimilardocumentsarenotplacedinclosephysicalproximitylikethecollectionsinaphysicallibraryorstoredinsomearchive.Internetdirectories,likeYahoo!,helporganizelinkstosimilardocumentstoeasetheretrievalproblem,butthecategorizationprocessisoftendonemanuallyandthisisexpensiveandtime-consuming.SincetheWebisahypertext/hypermediasystemandwedonotpossesstheresourceswhichInternetdirectoriesdo,thenaturalwayofreachingsimilardocumentsfromgivendocumentswouldbetotraversethelinksonthelatter.AretrievaltoolfortheWebshouldexploitthelinksintheWebdocuments(i.e.Webpages)initssearchfordocumentsrelevanttoauserrequest.Informationrange.SomeconventionalIRsystemscontainspecial-izedinformation,suchas,forexample,medicaldocumentation,orpatents.Hence,IRsystemscansometimesexploitdomainknowledgetoenhanceretrievalperformance.Incontrast,thesubjectrangeofin-formationontheWebisverywide.AnyretrievalprogrambuiltfortheWebmustbeexibletoretrieveinformationofawiderangeofsubjectsandwrittenindierentnaturallanguages.Retrievalmodelsthatex-ploitassociationsbetweendocumentsareappropriateforretrievalontheWebbecausethesemodelsdonotdictatethetopicalrangeofrele-vantinformationprovidedatthebeginningofthesearch.Theysimply3searchforsimilarinformationregardlessofthetopicofthequery(Ellis,1996).Changeofcontent.TheWebisaverydynamicinformationcollec-tion.Everysecond,changesarebeingmadetoexistingWebpages,andpagesareaddedtoordeletedfromtheWeb.ConventionalIRsystemsarelessdynamicandthereismuchmorecontroloverthechangesmadetothedocumentcollection.AretrievalsystemfortheWebshouldbeabletoretrievedocumentsthatareup-to-dateandshouldnotrely(atleastnotcompletely)onindexesthatcouldbecomeoutdatedveryquickly.InthispaperwepresentaprototypeWebsearchsystemthatexploitstheabovedistinctionbetweendocumentsusuallymanagedbyIRsystemsandthosemanagedbytheWeb.TheunderlyingIRmodelofthisprototypeisavariationofthemodelknownasAssociativeRetrieval.AssociativeRetrievalwasrstintroducedbySalton(1968)andisconcernedwithexploitingasso-ciationsbetweeninformationitemsatretrievaltime.Associationsarerstdeterminedusingcitationsorstatisticaltechniques(likeforexampletermco-occurrence)andthenusedbycomplexretrievalfunctions.Intheworkpresentedinthispaperwedonotusecitationsorstatisticalassociations,butweusetheexistingassociationsrepresentedbyhypertextlinksbetweenWebdocuments.WhatweconsiderimportantofAssociativeRetrievalistheideabehindthisformofretrieval,i.e.thatitispossibletoretrieverelevantdocumentsbyretrievingthosethatareexplicitlyassociatedwithsomethattheuserknowstoberelevant.TheworkpresentedinthispaperintegratesAssociativeRetrievalwithOs-tensiveRetrieval.ThisnovelapproachtoIRwasproposedbyCampbellandVanRijsbergen(1996)andisconcerned