萨师煊国际大数据分析与研究中心.ppt

WeiyiMeng孟卫一DepartmentofComputerScienceStateUniversityofNewYorkatBinghamtonJuly9 2012 Large ScaleDistributedInformationRetrievalontheWeb 萨师煊国际大数据分析与研究中心SummerResearchCampSeminar AboutSUNY Binghamton Foundedin1946afterWWII LocatedinBinghamton acityinSouthernTierofNewYorkStateAbout15 000students 3 000gradstudents IBMwasfoundedinBinghamtonOneofthe4UniversityCentersofSUNYsystem SUNYatStonyBrook SUNYatBuffalo SUNYatAlbany Formoreinformation seehttp www2 binghamton edu features premier index html WhatisInformationRetrieval Informationretrieval IR isacomputersciencedisciplineforfindingunstructureddata usuallytextdocuments thatsatisfyaninformationneedfromwithinlargecollectionsthatarestoredoncomputers Inthisseminar wearegoingtoextendthisdefinitiontoincludebothunstructuredandstructureddata WhatisDistributedInformationRetrieval DIR ItisaspecialbranchofinformationretrievalwherethedataoftheIRsystemarestoredinmultipledistributedlocations collections IntheWebenvironment DIRdealswithdatathataredistributedacrossmanywebsitesorwebservers RelatedtermsforDIR metasearchengine federatedsearch webDBintegrationsystem TheScale HowLarge ItcanbeaslargeasthenumberofdatasourcesontheWeb A2007survey Madhavanetal 2007 indicatestherewereabout50millionsearchableWebdatasourcesin2007 25millionforun orlessstructureddata webpages weibo 25millionforstructureddata webdatabases WheredoWebdatareside IcebergStructure AsmallfractionisontheSurfaceWebwithmostlystaticwebpagesthatarecrawlablebyfollowinghyperlinks Publiclyindexableportion 40 60billionpagesMostareintheDeepWebwithbothstructureddataandlessstructuredtextdocumentshiddenbehindnumeroussearchinterfaces About1trillionpages records TwoparadigmstoprovideintegratedaccesstoWebdata Crawling based GatherWebdatafromvariousWebserversand orsearchenginesandbuildasearchindexforthegathereddata SurfaceWebcrawlingDeepWebcrawlingMetasearching based DIR based Integrateexistingsearchenginesintofederatedsystems MetasearchingtextdocumentsMetasearchingstructureddatabydomain Advantagesofeachapproach Crawling based Completecontroloncrawleddata CanaddmetadataCanlinkdatafromdifferentsourcesinadvanceCancreateanarchivegraduallyCompletecontrolonretrievingtechniquesandrankingfunctionsFastresponsetime Metasearching based CapabilitiesofsearchenginescanbeleveragedNaturalclusteringofthedatabyindividualsearchenginescanbeutilizedThree levelqueryevaluationprocess SEselection SEretrieval resultmerging canleadtobettereffectivenessMorelikelytoobtainfresherresults Disadvantagesofeachapproach Crawling based DeepWebcrawlingdifficultOftenincompleteManysitesnotcrawlableLosesemantics structureofthedataCannotleveragesearchengines capabilitiesCrawlingdelayleadstolessup to dateresultsCopyrightandprivacyissues Metasearching based PerformancedependsonthequalityofusedsearchenginesMaycausesearchenginestocrashAccesscouldbeblockedbysearchenginesNodirectcontrolofthedataSlowerresponsetime Conclusions Bothtechnologies crawling basedandmetasearching based haveuniquevaluesandtheyshouldco exist Theyactuallycomplementeachother Question Isthereaneffectivewaytocombinebothtechnologiesintoasingleplatform Ourseminarwillfocusonthemetasearching DIR basedapproach Twotypesofmetasearchingsystems Becausestructuredandunstructureddatahaveverydifferentcharacteristics theyareoftenhandledseparatelywithdifferenttechnologies Metasearchingsystemsfortextdocuments metasearchenginesorDIRsystems Metasearchingsystemsforstructureddata eachforagivendomain Webdatabaseintegrationsystems Wewillfirstintroducelarge scalemetasearchenginesandthenintroducelarge scaleWebdatabaseintegrationsystems Duetolimitedtime wewillfocusonchallengesandremainingchallenges notoncurrentsolutions Large ScaleMetasearchEngines MSE useruserinterfacequerydispatcherresultmergersearchsearchsearchengine1engine2enginen texttexttextsource1source2sourcen query result AsimpleMSEarchitecture Whatisalarge scaleMSE Alarge scalemetasearchengineneedstosatisfyALLofthefollowingrequirements Itisametasearchengine Itisconnectedtoalargenumberof thousandsormore componentsearchengines Thecomponentsearchenginesarespecial purposesearchenginesCoveringaspecificdomain news sports medicine Coveringaspecificorganization RenDa IBM ACM Whythethirdrequirement ToretaintheadvantagesonfreshnessandsearchingthedeepWeb Technicalchallengeswithlarge scaleMSE ScalableandaccuratesearchengineselectionMostsearchenginesareuselessforagivenuserquery Best10results 10 000searchengines atleast9990useless UsinguselesssearchenginesisbadUnnecessarynetworktrafficWasteresourcesoflocalsearchenginesIncurhighercostatthemetasearchengineLeadtopooreffectivenessHowtoidentifythemostappropriatesearchenginesforanygivenqueryaccuratelyandinatimelymanner Howtosummarizeasearchenginecontent representative Howtocollecttherepresentative Howtousetherepresentativestoperformselection Technicalchallenges cont AutomaticsearchengineinclusionintometasearchengineAutomaticconnectiontosearchengines automaticconnectionwrappergeneration SubmitqueriesandreceiveresultpagesviaprogramAutomaticsearchresultrecords SRR extraction automaticextractionwrappergeneration AutomaticwrappermaintenanceSearchenginesmaychangetheconnectionparametersandandresultpresentationanytime Technicalchallenges cont EffectiveandefficientresultmergingAutonomouscomponentsearchengineslikelyemploydifferentmatchingtechniquesbetweenqueriesanddocuments indextechniques weightingschemes similarityfunctions link basedranking etc LocalscoresandranksaregenerallynotcomparableHowtore ranktheresultsreturnedfromdifferentsearchenginesintoasinglerankedlistsuchthathigheffectivenesscanbeachievedinaspeedymanner Large scaleMSEarchitecture SearchEnginem SearchEngineSelector QueryDispatcher ResultMerger ResultCollectorandExtractor SearchEngine1 SearchEngineRepresentatives Userquery WorldWideWeb Web SearchEngineDiscovery SEList SEIncorporation Automaticconnectionandresultextraction MetasearchEngineConstructionModule QueryProcessingModule Result SearchengineRepresentativesGeneration TwoRecentBooks Monographs W MengandC Yu AdvancedMetasearchEngineTechnology Morgan ClaypoolPublishers December2010 MetasearchenginearchitectureSearchengineselectionSearchengineincorporationResultmergingSummaryandFutureResearch TwoRecentBooks Monographs M ShokouhiandL Si FederatedSearch FoundationsandTrendsinInformationRetrieval 5 1 pp 1 102 2011 Tableofcontent IntroductionCollectionrepresentationCollectionselectionResultmergingFederatedsearchtestbedsConclusionandFutureResearchChallenges SearchEngineSelection 1 Problem Givenanyuserqueryandasetofsearchengines ordocumentcollections determinethesearchenginesthatmatchtheuserquerythebest Basicsolution Summarizethecontentofeachsearchengineinadvance Foreachuserquery compareitwiththesearchenginesummariesandcomputeamatchingscore Ranksearchenginesindescendingorderoftheirmatchingscoreswiththequeryandselectthetop rankedsearchengines SearchEngineSelection 2 Question1 Howtosummarizethecontentofeachsearchengines Advancedsolutionsarestatistics based Oneormorestatisticsforeachterminthedocumentsofasearchengine Someusedstatisticsforatermt documentfrequency df Thenumberofdocumentsinthesearchenginethatcontaint collectionfrequency cf Thenumberofsearchenginesinametasearchenginethatcontaint averagenormalizedweight anw TheavgoftheweightsoftinalldocumentscontainingtinaSE maximumnormalizedweight mnw ThemaxoftheweightsoftinalldocumentsinaSE SearchEngineSelection 3 Question2 Howtoobtainthesummariesofsearchengines Twogeneralscenarios Straightforwardcomputationifthedocumentsofthesearchengineisavailable Query basedsamplingifthedocumentsofthesearchenginearenotdirectlyavailable i e deepwebsearchengine Manypublishedsolutions butstillnotscalabletolarge scalemetasearchengines SearchEngineSelection 4 Question3 Howtoranksearchenginesforeachuserquery Sub questions Howtodefineameasureofusefulnessofasearchenginewithrespecttoaquery Howtocomputethemeasureveryquickly highlyefficiently inalarge scalemetasearchengine Alargenumberofsearchengineselectionalgorithmshavebeenproposed mostarenotveryscalable AutomaticconnectiontoanysearchenginegivenitsURLPassqueriestothesearchengineprogrammatically Receiveresultsfromthesearchengineprogrammatically AutomaticextractionofretrievedsearchresultsExtracttheURLsandsnippetsofretrievedpages ExtractthenumberofhitsExtracttheURLpatternofthenextpagebutton AutomaticconnectionandextractionmaintenanceAutomaticfailuredetection AutomaticSearchEngineIncorporation ExtractconnectionparametersfromtheHTMLformtagofeachsearchengine ApplyHTTPrequestmethod GETorPOST toperformconnection AutomaticSearchEngineConnection ComplexsearchformswithmanycontrolelementsIll formattedHTMLsearchformsMultiplesearchformsonthesamepageSearchformswithJavaScriptand orCSS cascadingStyleSheets SearchformsthathaveactionredirectionsSearchformsthatutilizesessions cookiesSearchenginesthatdonotallowmetasearching Searchformextraction Difficulties Asearchresultrecord SRR consistsofthereturnedinformationassociatedwitharetrievedWebpage URLofthepageTitleofthepageAshortsummaryofthepageOthermisc size date category Resultpagesoftencontainirrelevantinformationsuchasthatrelatedtoadvertisementandhostingorganization inadditiontoSRR AutomaticSearchResultRecords SRRs Extraction 1 WebScales WrapperGeneration anSRR anSRR ExtractcorrectSRRsfromreturnedresponsepageswhilediscardingirrelevantinformation Theproblemistoidentifytherules oftencalledwrapper thatcanextractthecorrectSRRs AutomaticSRRExtraction 2 GeneralmethodologyUtilizethetagstrings DOMtrees visualinformationononeormoreresultpagesfromthesamesearchenginetomineextractionpatterns Identifytheminimaldata richregion subtreethatlikelycontainstheSRRs Identifyseparator s thatseparatedifferentSRRs Morerecentsolutionsusemorevisualinformationonresultpages Stillcannothandlecomplexresultpageswell javascript multiplecolumns multiplesections multipleSRRformats AutomaticSRRExtraction 3 ResultMerging 1 Problem Mergereturneddocumentsfrommultiplesourcesintoasinglerankedlist DifficultiesFulldocumentsofsearchresultsarenotavailableortooexpensivetodownloadandanalyzeonthefly Localsimilarities thuslocalranks areusuallynotcomparableduetodifferentsimilarityfunctionsdifferenttermweightingschemesdifferentstatisticalvalues e g globalidfvs localidf ResultMerging 2 Alargenumberofsolutionshasbeenproposedtoperformresultmerging Someuselocalsimilaritiesassociatedwitheachresult modernsearchenginesnolongerprovidetheinformation Someuselocalranksofsearchresults Someanalyzedownloadedfulldocuments Someusethetitlesandsnippetsofthesearchresults Someconsiderthequalityoftheusedsearchengine Someconsiderwhetheraresultisretrievedfrommultiplesearchengines Someuseasamplesetofdocumentsfromeachsearchengine Informationthatcouldbeutilizedforresultmerging LocalsimilarityorlocalrankofeachresultTitleofeachresultSnippetofeachresultPublicationtimeofeachresultOrganization personwhopublishedtheresult fromURL SizeofeachresultNumberofsearchenginesthatreturnedtheresultRankingscoresofthesearchenginesthatreturnedtheresultFullcontentofeachresult orsomeoftheresults PageRankornumberofbacklinksofeachresultAsamplesetofdocumentsfromeachsearchengine ResultMerging 3 RemainingResearchChallenges 1 SearchenginesummarygenerationandmaintenanceQuery basedsamplingmethodshavenotbeenshowntobepracticallyviableforalargenumberoftrulyautonomoussearchengines Certainstatisticsusedbysomesearchengineselectionalgorithms suchasthemaximumnormalizedweight arestilltooexpensivetocollectasitmayrequiresubmittingasubstantialnumberofqueriestocoverasignificantportionofthevocabularyofasearchengine Theimportantissueofhowtoeffectivelymaintainthequalityofsummariesforsearchengineswhosecontentsmaychangeovertimehasstartedtogetattentiononlyrecentlyandmoreinvestigationintothisissueisneeded RemainingResearchChallenges 2 Automaticsearchengineconnectionwithcomplexsearchforms Moreandmoresearchenginesareemployingmoreadvancedtoolstoprogramtheirsearchforms Forexample moreandmoresearchformsnowhaveJavascripts Somesearchenginesalsoincludecookieandsessionidintheirconnectionmechanism Thesecomplexitiesmakeitsignificantlymoredifficulttoautomaticallyextractallneededconnectioninformation RemainingResearchChallenges 3 Automaticmaintenance Searchenginesusedbymetasearchenginesmaymakevariouschangesduetoupgradeorotherreasons Possiblechangesmayincludesearchformchange queryformatchange andresultdisplayformatchange Thesechangescancausethesearchenginesnotusableinthemetasearchenginesunlessnecessaryadjustmentsarem