资源描述：
《Fast_Set_Intersection_in_Memory》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、FastSetIntersectioninMemoryBolinDingArndChristianKonig¨UniversityofIllinoisatUrbana-ChampaignMicrosoftResearch201N.GoodwinAvenueOneMicrosoftWayUrbana,IL61801,USARedmond,WA98052,USAbding3@uiuc.educhrisko@microsoft.comABSTRACTrithmsbecomepossible,whichoftenoutperforminvertedindexes;e.g.,usinghash-ba
2、seddictionaries,intersectingtwosetsL1,L2SetintersectionisafundamentaloperationininformationretrievalrequiresexpectedtimeO(min(jL1j;jL2j)),whichisafactorofanddatabasesystems.Thispaperintroduceslinearspacedatastruc-(log(1+max(jL1j=jL2j;jL1j=jL2j)))betterthanthebestpos-turestorepresentsetssuchthatth
3、eirintersectioncanbecomputedsibleworst-caseperformanceofcomparison-basedalgorithms[6].inaworst-caseefficientway.Ingeneral,givenk(preprocessed)Inthiswork,weproposenewsetintersectionalgorithmsaimedatsets,withtotallynelements,wewillshowhowtocomputetheirpfastperformance.Theseoutperformthecompetingtechn
4、iquesforintersectioninexpectedtimeO(n=w+kr),whereristhein-mostinputsandarealsorobustinthat–forinputswheretheyaretersectionsizeandwisthenumberofbitsinamachine-word.Innotoptimal–theyareclosetothebest-performingalgorithm.Theaddition,weintroduceaverysimpleversionofthisalgorithmthattradeoffforthisgaini
5、saslightincreaseinthesizeofthedatastruc-hasweakerasymptoticguaranteesbutperformsevenbetterinprac-tures,whencomparedtoaninvertedindex;however,inuser-facingtice;bothalgorithmsoutperformthestateofthearttechniquesforscenarioswherelatencyiscrucial,thistradeoffisoftenacceptable.bothsyntheticandrealdatas
6、etsandworkloads.1.1Contributions1.INTRODUCTIONOurapproachleveragestwokeyobservations:(a)IfwisthesizeFastprocessingofsetintersectionsisakeyoperationinmany(inbits)ofamachine-word,wecanencodeasetfromauniversequeryprocessingtasksinthecontextofdatabasesandinformationofwelementsinasinglemachineword,allo
7、wingforveryfastin-retrieval.Forexample,inthecontextofdatabases,setintersectionstersections.(b)Forthedatadistributionsseeninmanyreal-lifeex-areusedinthecontextofvariousformsofdatamining,textanalyt-amples(inparticu
