基于主题划分的有组织P2P搜索算法

3912200512JOURNALOFXI'ANJIAOTONGUNIVERSITYVol.39№12Dec.2005P2P1,2,1,3,1(1.,710049,;2.,518060,;3.,100084,):P2P---(TONS).TONSP2P,,,P2P.,Small-World.TONSP2P、,P2P,74.7%,P2P.:;;;P2P:TP393:A:0253!987X(2005)12!1327!04DistributedInformationSearchBasedonTopicPartitioninStructuredPeer-to-PeerNetworksFuXianghua1,2,FengBoqin1,UaZhaofeng3,ZeUing1(1.SchoolofElectronicsandInformationEngineering,Xi'anJiaotongUniversity,Xi'an710049,China;2.FacultyofInformationEngineering,ShenzhenUniversity,Shenzhen518060,China;3.DepartmentofComputerScienceandTechnology,TsinghuaUniversity,Beijing100084,China)Abstract:Atopicoverlaynetworksearch(TONS)algorithm,P2Psearchmechanismbasedontopicparti-tion,ispresented.Onthebasisofthestructurednetworks,thenodesareorganizedasanoverlaynetworkaccordingtotopicssuchthatthenodescontainingsimilartopicarelinkedtogether.Thus,thequerycon-tentscanbelimitedinthelocalrangeofP2Pnetworkandtheoverlaynetworkhassmallworldtraitsbyrandomlyaddingsomelongdistancelinksintheoverlaynetwork.TONSprovidesstructuredP2Pnetworkswitheffectiveapproachtosearchfornodedataobjectsbasedoncomplicatedquerieswithpartialmatchandmultiplekeywords.Comparedwiththeexistingstructuredsystems,TONSincreasesthesearchrecallby74.7%,andreducestheaveragepathdistanceandtheaveragenumberofmessagesduringthesearchingprocess.Keywords:topicoverlaynetwork;topicpartition;informationsearch;structuredP2PnetworkP2PO(lgN)(N)[1!4],、.P2P,[5!7],P2P[8].,,,P2P、.:2005!01!22.:(1977),,;(),,,.:(2003AA1Z2610).1,.,,.P2PT={tk|1≤k≤\},pi(1≤i≤N)T(pi),.P2P,pi‘(pi).n,2pips,L=1n(n-1)/2Σ1≤i,s≤NDist(pi,ps)tk(1≤k≤\),,tkW(tk),|W(tk)|.,,.,.F,|F|.,.:),;*,.,,,,.1,12.,(Topic,No-deID,NodeProperty,Overlay).:Topic,T;NodeID,N;NodeProperty,{preceeding,successor,shortcut},preceeding,successor,shortcut;Overlay,{bW,bF},bW,bF.22.1pi],(BTONS),,.$r,pi],.(1)pi,],.(2)]T(pi),piW(tk)]$rtk,].(3)pi]$r,piR1].(4)R1F]$r,R(tk);R1]$r,R2,R2].,]$rR(tk).(5)R(tk)F]W(tk),,,,W(tk)d.(6)W(tk)]pi.BTONS,P2P.P2PO(lgN),]FO(|F|),W(tk)O(|W(tk)|).,O(|F|)+O(|W(tk)|).2.2Small-WorldBTONSBTONS,.BTONS,Small-World.WS[9],n,,h,h,P,.P0,L～n2h,;0.001P0.01,L～lnnlnh,,,L,Small-World.823139Kleinberg[10]Small-World,,O(lg2n);Symphony[6]Kleinberg,h=O(1),O1hlg2()n.n[0,1],h≥1.:P(x)x∈[0,1],xpi,pi.P(x):x∈[1/n,1],P(x)=1/(xlnn),P(x)=0.BTONSTONS,TONS,]FO1hlg2|F()|,W(tk)(O1h·lg2|W(tk))|,O1hlg2|F()|+(O1hlg2|W(tk))|.2.3P2P.pi|T(pi)|,2、2h1,|T(pi)|(2h+3),2h+2.P2P,.pi,.(1)pi,T'(pi),T,T(pi).(2)R(tk)Uadd,FT(pi)R(T(pi)).(3)R(T(pi))UaddW(T(pi)),W(T(pi)),pj.(4)pjUadd,piS(pj),pi,Uupdate,P(x).(5)piS(pj),S(pi),P(x).piW(T(pi)),piS(pi)Uleft,.33.1P2PChord[2]P2P.,34178,32;500,500,,.,8,18.,3:)!(])(]);*?U;+L.a,b,c,!(])(])!(])=cb(])=ca3.23P2PSNS,SNS、BTONSTONS3,1.BTONSTONS10,32,d=20,$l=0.01.1,SNS,,14.6%.P2P,P2P,BTONS85.7%,TONS89.3%,,,.1,,P2P,SNS25.13BTONS22.86923112,:P2PTONS18.38,SNS10.87BTONS8.56TONS5.93.BTONSTONS,,、,.13!/%/%?ULSNS14.689.425.1310.87BTONS85.782.522.868.56TONS89.382.818.385.933.3P2P,P2P.P2P,2,1.P2P,,,,.,.1,30%,,,;30%,,,.14P2P,,.P2P,,.:[1]StoicaI,MorrisR,KargerD,etal.Chord:ascalablepeer-to-peerlookupserviceforInternetapplications[A].ACMSIGCOMMConference,SanDiego,USA,2001.[2]RatnasamyS,FrancisP,HandleyM,etal.Ascala-blecontent-addressablenetwork[A].ACMSIG-COMMConference,SanDiego,USA,2001.[3]RowstronA,DruschelP.Pastry:scalable,distribu-tedobjectlocationandroutingforlarge-scalepeer-to-peersystems[A].IFIP/ACMInternationalConfer-enceonDistributedSystemsPlatforms.Heidelberg,Germany,2001.[4]MankuGS,BawaM,RaghavanP.Symphony:dis-tributedhashinginsmallworld[A].4thUSENIXSymposiumonInternetTechnologiesandSystems,Se-attle,USA,2003.[5]ZhouF,ZhuangL,ZhaoBY,etal.Approximateob-jectlocationandspamfilteringonpeer-to-peersystems[A].ACM/IFIP/USENIXInternationalMiddlewareConference,RiodeJaneiro,Brazil,2003.[6]ReynoldsP,VahdatA.Efficientpeer-to-peerkeywordsearching[A].ACM/IFIP/USENIXInternationalMiddlewareConference,RiodeJanerio,Brazil,2003.[7]TangCQ,XuZC,DwarkadasS.Peer-to-peerinfor-mationretrievalusingself-organizingsemanticoverlaynetworks[A].ACMSIGCOMMConference,Karlsruhe,Germany,2003.[8]DaswaniN,Garcia-MolinaH,YangB.Openprob-lemsindata-sharingpeer-to-peersystems[A].9thIn-ternationalConferenceonDatabaseTheory,Siena,It-aly,2003.[9]WattsDJ,StrogatzSH.Collectivedynamicsofsmallworld-worldnetworks[J].Nature,1998,393(6684):440!442.[10]KleinbergJ.Thesmall-worldphenomenon:analgo-rithmicperspective[A].32ndACMSymposiumonTheoryofComputing,Portland,USA,2000.()033139