节点贝尔金无线路由器

ISSN1000-9825,CODENRUXUEWE-mail:jos@iscas.
ac.
cnJournalofSoftware,Vol.
17,No.
4,April2006,pp.
782793http://www.
jos.
org.
cnDOI:10.
1360/jos170782Tel/Fax:+86-10-625625632006byJournalofSoftware.
Allrightsreserved.
混合P2P环境下有效的查询扩展及其搜索算法张骞+,张霞,刘积仁,孙雨,文学志,刘铮(东北大学计算机软件国家工程研究中心,辽宁沈阳110179)QueryExpansionandItsSearchAlgorithminHybridPeer-to-PeerNetworksZHANGQian+,ZHANGXia,LIUJi-Ren,SUNYu,WENXue-Zhi,LIUZheng(NationalEngineeringResearchCenterforComputerSoftware,NortheasternUniversity,Shenyang110179,China)+Correspondingauthor:Phn:+86-24-83661102,E-mail:zhangqian@neusoft.
com,http://www.
neu.
edu.
cnZhangQ,ZhangX,LiuJR,SunY,WenXZ,LiuZ.
Queryexpansionanditssearchalgorithminhybridpeer-to-peernetworks.
JournalofSoftware,2006,17(4):782793.
http://www.
jos.
org.
cn/1000-9825/17/782.
htmAbstract:QueryexpansionhaslongbeensuggestedasatechniquefordealingwiththefundamentalissueofwordmismatchininformationretrievalandithasgainedgreatsuccessinWebsearching.
However,processingqueryexpansionisverychallenginginhybridP2PnetworkbecauseaP2Psystemisadecentralizedanddynamicsystem.
First,theLEMqueryexpansionmethod,whichisconstructedbyanalyzingcorrelationbetweenqueriesanddocuments,ispresented.
Andthen,theHEMqueryexpansionmethodisproposedbyestablishingthecorrelationbetweenqueriesanddocumentstermsdirectly.
Next,anefficientsearchalgorithmisconstructedbasedonthequeryexpansionalgorithms.
Itisprovedbyexperimentsthatthequeryexpansionmethodsandsearchalgorithmscangreatlyimprovethesearchefficiency.
Keywords:queryexpansion;peer-to-peer;querynote;similarity;search摘要:查询扩展是解决信息获取领域中用词歧义性问题的关键技术,并被广泛应用于搜索引擎中,获得了巨大的成功.
然而,由于P2P(peer-to-peer)系统是一个分散的、动态的系统,在P2P环境下进行有效的查询扩展具有一定的挑战性.
首先,利用查询与文档的关联关系构建了LEM(localexpansionmethod)查询扩展方法;然后,基于查询与文档用词的直接关联,提出了HEM(history_basedexpansionmethod)查询扩展方法.
在此基础上,提出了一种基于查询扩展的混合P2P环境下的搜索算法.
实验及分析结果表明,查询扩展及其搜索算法能够极大地提高搜索的效果.
关键词:查询扩展;peer-to-peer;查询记录;相关度;搜索中图法分类号:TP311文献标识码:APeer-to-Peer(P2P)是当前研究的热点.
目前,很多P2P系统支持基于关键词的搜索[1,2].
然而,由于大量同义词和多义词的存在,用户提交的查询用词往往与文档索引使用的词有很大差别,这就是所谓的"词典问题(dictionaryproblem)"[3].
"词典问题"的存在,限制了P2P系统的应用.
Furnas就"词典问题"所做的实验表明:两个人使用同样的关键词描述同一事物的概率通常小于20%.
同样SupportedbytheNationalHigh-TechResearchandDevelopmentPlanofChinaunderGrantNo.
2002AA4Z3120(国家高技术研究发展计划(863))Received2005-06-28;Accepted2005-10-10张骞等:混合P2P环境下有效的查询扩展及其搜索算法783有研究表明:网络用户用于检索的查询85%是短查询,该类查询一般包括3个或更少数目的查询单词[4].
因此,用户提交的查询通常不能充分表达出检索相关文档所需的信息.
目前,Web搜索引擎广泛采用自动查询扩展方法来解决这个问题,并获得了成功.
即在原来查询的基础上,加入与用户用词相关联的词组成新查询,这在一定程度上弥补了用户查询信息的不足.
我们希望使用P2P系统也能像使用Web搜索引擎那样,当输入一个查询时,系统能自动进行查询扩展,返回最相关的结果.
因此,在P2P系统中进行查询扩展优化十分必要.
由于P2P系统中不存在中心控制节点,网络中的节点也可以随意加入或退出系统,因此,在P2P环境下进行查询扩展优化是十分具有挑战性的.
本文提出了两种P2P环境下的查询扩展方法:局部查询扩展方法LEM(localexpansionmethod)和基于历史查询信息的查询扩展方法HEM(history_basedexpansionmethod).
设定的场景为非结构化文档上的基于关键字的查询.
本文第1节介绍现有的查询扩展技术,随后依次介绍局部查询扩展方法和基于历史查询信息的扩展方法,并在此基础上提出一种新的查询路由算法.
最后是仿真实验及分析.
1相关工作据我们所知,目前还不存在有效的P2P环境下的查询扩展方法.
因此,这里对传统的查询扩展技术作简要介绍.
查询扩展技术主要分为全局分析与局部分析两类.
全局分析的基本思想是统一对全部文档中的词或词组进行相关性分析,计算词或词组与查询之间的相关度.
当查询到来时,使用与查询相关度最高的文档用词作为新生成的查询用词.
LSI(latentsemanticindexing)[5]等是常见的全局分析方法.
该类方法的主要缺陷在于:对于非常大的文档集,构建全局性的词关系词典通常在时间和空间上是不可行的,并且词典的更新将产生较高的代价.
显然,这不适合文档数量巨大及高度动态的P2P网络.
局部分析可以进一步分为相关反馈(relevancefeedback)[6]和局部反馈[7]两类.
相关反馈需要用户对初次检索的结果进行评判,然后从用户认为相关的文档中选择扩展用词.
局部反馈不需要用户的参与,它从初次检索的前N篇文档中选择扩展用词.
但局部反馈的查询精度高度依赖于排在前面的文档与查询的相关度:当相关度不大时,局部反馈会把大量无关的词作为扩展用词,从而降低了查询精度.
在P2P网络中,由于节点在计算能力、网络带宽等方面的异质(heterogeneity)性,并非每个节点都适合直接采用局部分析的方法进行查询扩展.
Xu将全局分析的技术应用于局部反馈,提出了局部上下文分析方法[8],研究表明,该方法的检索效果优于传统的全局分析和局部分析方法.
因为本文提出的LEM方法是对局部上下文分析方法的修改,因此,这里对局部上下文分析方法进行详细描述.
该方法的基本思想是:从初始检索得到的前N篇文档中选择与原查询相关度最高的文档用词作为新的查询用词,相关度依据下式计算iiidfcQtiNidftccfcQsimi])log()1),([log(),(δ+*+=∏∈(1),),(1,∑===Njjjjiifcfttccfidfi=max(1.
0,log10(N/Ni)/5.
0);idfc=max(1.
0,log10(N/Nc)/5.
0).
其中:simi(Q,c)为查询与词或词组的相关度;cf(c,ti)表示查询用词和文档用词共同出现的频率;Ni和Nc分别是包含查询用词ti和文档用词c的文档数目.
选取m个相关度最高的文档用词作为新的查询用词.
2混合P2P网络混合P2P网络中存在两类节点:目录节点(directorynode)和叶节点(leafnode).
相对于叶节点,目录节点具有更高的可信度,在网络中担负更大的责任.
叶节点以"星型"方式连接到目录节点上,叶节点发起的查询首先被路由到目录节点,由目录节点依据一定的策略路由查询,最后有目录节点收集查询结果并返还给叶节点,叶节点在结果中选择并通过点击连接直接下载文档.
如图1所示,叶节点C发出查询请求,图中的箭头表明查询结果的返回路径,目录节点D负责对叶节点F,G及目录节点E返回的查询结果进行合并,并将合并后的结果返回给C,C依据自己的判断点击连接直接下载文档.
下面给出P2P环境下查询记录的定义.
JournalofSoftware软件学报Vol.
17,No.
4,April2006784定义1.
令Note为节点保存的历史查询记录,即Note=(querytext)[(Di,IDi,D_WORDi)]…其中,(querytext)为Note对应的查询;Di为用户从标识为IDi的Peer节点下载的文档集.
将每个文档中诸如a,the,is等出现频率极高的词删除,组成文档词集D_WORDi.
每次查询用户可能从多个节点下载文档,因此每条查询记录可能包含多个(Di,IDi,D_WORDi)对.
CAFDEGFig.
1RetrievalinhybridP2Pnetworks图1混合P2P环境下的信息获取基于上述定义,易得下述假定是合理的:(1)Di代表的文档集与(querytext)具有很强的相关性.
用户浏览搜索结果并点击下载文档,这一行为本身就包含着用户对文档和查询之间相关性的判断;(2)(querytext)中包含的查询单词与D_WORDi包含的文档单词具有很强的相关性.
这种相关性可以作为选择查询扩展词的依据;(3)若历史记录中标识为IDi的节点与查询单词及其扩展词有较强的关联关系,则认为该节点拥有的文档与查询具有很强的相关性.
基于上述假定,可以建立查询空间、文档空间、文档用词和Peer节点间的关联关系,利用这些关系可以进行有效的查询扩展及搜索.
后续章节将对此详加论述.
3LEM扩展方法本节试图对局部上下文分析方法进行修改,使之适用于混合P2P环境.
由于弱Peer节点的存在,该类节点一般具有弱的计算力和存储力,因而通常不能在该类节点上直接应用局部上下文分析方法;另一种可能的方法是充分利用目录节点的计算及存储优势,在目录节点上应用局部上下文分析方法,即由叶节点发送查询到与之连接的目录节点,由目录节点采用局部分析方法对查询进行扩展.
然而,该方法仍然面临以下挑战:(1)由第1节的分析可知,局部上下文分析方法的应用效果高度依赖于初次检索得到的文档.
因此,问题的关键是如何在目录节点上确定与查询最相关的N篇文档;(2)每次都需要先进行初始检索,然后利用初始检索得到的前N篇文档进行查询扩展.
这不仅浪费了网络资源,而且不利于提高用户满意度.
问题转化为在不进行初次检索的情况下,如何在目录节点上获取与查询最相关的N篇文档.
我们的方法是:每次查询完成后,叶节点将查询记录发往相应的目录节点.
目录节点利用保存的历史查询记录构造查询用词空间和文档空间的关联关系(如图2所示),当新查询到来时,利用这种关联关系获取与查询最为相关的N篇文档.
Notes0.
550.
50.
30.
60.
50.
50.
4.
.
.
.
.
.
.
.
.
QuerytermsDownloaddocuments.
.
.
0.
520.
420.
50.
50.
30.
4.
.
.
QuerytermsDownloaddocumentsFig2.
Correlationbetweenquerytermsanddownloaddocuments图2查询用词空间与文档空间的关联关系在查询记录中,若查询用词ti与文档Dc间至少存在一条可达路径,则创建一条ti与Dc的直接连接,并依据ti与Dc的相关程度为该连接赋予一定的权重.
对任意查询用词ti与文档Dc,关联权重记为Weighti,c,可以通过两者在历史查询记录中出现的频率来估算.
iciiciciciITtfDtfWeight**=,,,)(),((2)张骞等:混合P2P环境下有效的查询扩展及其搜索算法785.
)0.
1log()/)5.
0log((,)_/(,,,++=+=nnfnIqwavgqwqfqfTiiccicici其中,fi,c(ti,Dc)是查询用词ti与文档Dc同时出现的历史记录数目;f(ti)是ti出现的历史记录数目;qfi,c是ti在文档Dc中出现的频率;qwc是Dc包含的单词数目;avg_qw是历史记录中全部文档包含的平均单词数目;Ii类似于反排文档索引;nfi是历史记录中包含ti的文档数目;n是历史记录中包含的总的文档数目.
fi,c(ti,Dc)的含义是:如果ti与Dc以较高的频率共同出现,则认为ti与Dc高度相关;Ti,c和Ii分别类似于CORI[9]资源选择算法中的Ti和Ii,即ti相对于Dc的权重与ti在Dc中出现的频率成正比,与包含ti的文档数目成反比.
当新查询到来时,利用查询用词空间与文档空间的关联关系计算查询与文档的关联度,计算方法借鉴了文献[9]中的方法.
∑==||1,||1),(QicicWeightQDQscore(3)其中,score(Q,Dc)是查询Q与文档Dc的关联度.
根据关联度,可以选择出与Q最为相关的N篇文档,然后利用局部上下文分析方法,从N篇文档中选取与Q最为相关的m个词或词组加入原查询组成新查询.
显然,历史记录信息越丰富,其包含的用户关于查询用词与文档的关联性判断就越多,就越有利于提高查询扩展的效果.
但对于某些新加入的节点,这类节点通常只有少量的历史查询记录,因而影响到扩展的效果.
另外,查询记录是随时间推移递增的,这可能会给某些弱节点带来严重的存储负担.
因此,在每次查询完成之后,叶节点需要将查询记录发往相应的目录节点,由目录节点构建查询用词空间与文档空间的关联关系,查询扩展在目录节点上进行.
4HEM扩展方法第3节在目录节点上建立了查询用词空间与文档空间的关联关系.
实际上,可以借助文档空间将查询空间与文档用词空间直接关联起来,查询单词与文档单词的关联权重可作为选择查询扩展词的依据[10].
设历史记录中包含的文档集为D,查询用词A与文档用词B的关联权重设为B相对于A的条件概率[10],P(WB|WA)=P(WB,WA)/P(WA)=)(),,(ADiBAWpdWWPid∑∈(4)其中,P(WB,WA,di)=P(WB|WA,di)*P(WA,di)=P(WB|WA,di)*P(di|WA)*P(WA).
P(WB|WA,di)可根据di在记录中出现的频率及A和B在di中的频率得出P(WB|WA,di)=)()()()(,,DcountdcountdsizeFDdsizeFDiiAiiBi**.
其中,FDi,A和FDi,B分别为单词A与B在文档di中的频率;size(di)为文档di的大小.
count(D)为整个历史记录中总的文档数目.
count(di)为di在全部历史记录中出现的数目;P(di|WA)表示在A出现的情况下di出现的概率,可以根据di与A在历史记录中同时出现的频率计算得出P(di|WA)=)(),(AiAWfdWf.
其中,f(WA)为包含A的记录数目;f(WA,di)为同时包含di和A的记录数目.
于是P(WB|WA)=∑*FDFD(5)∈**DdAiAiiAiiBiiWfdWfDcountdcountdsizedsize)(),()()()()(,,然后,可以计算单词B与查询Q的相似度score(Q,B).
∑∈=QAABWWPQBQscore)|(||1),((6)对任意查询Q,针对历史记录中的全部文档用词,根据式(6)计算用词与Q的相似度,并将结果按降序排列,选择相似度大于某一阈值σ的前m个结果作为Q的新扩展词.
与LEM方法一样,HEM方法也要求在每次查询完成后,叶节点需要将查询记录发往相应的目录节点,查询扩展在目录节点上进行.
5查询记录的获取及更新每次查询完成之后,LEM和HEM方法都要求叶节点将查询记录发往目录节点,而查询记录有查询单词、786JournalofSoftware软件学报Vol.
17,No.
4,April2006文档单词及Peer标识组成,因而产生较高的通信开销.
这里采用如下方法来减少这种开销:(1)叶节点发起的查询路由到达与之连接的目录节点时,目录节点保存该查询的一个副本.
这样,可以避免查询单词的重复发送;(2)叶节点下载的文档可能是其邻居节点已经下载过的,因而该文档所包含的单词在目录节点上已经存在,所以叶节点没有必要重复发送这些文档单词.
具体方法是:目录节点考察返回的查询结果R,并检查保存的查询记录N,若存在非空文档集合D,满足D∈R∩N,则将R中包含的与D中文档相关的结果作上已"获取过"标识"retrieval",并对所有结果进行编号(记为result_idi).
然后,将R返回给查询发起节点;(3)有研究表明[11],文档单词的重要性与其频率的排序往往满足Zipf定律.
因此,在文档中仅出现1次的单词数量往往占据总单词数量的一半,抛弃对这些单词的传输可以使通信代价大为减少;(4)叶节点计算本次查询涉及到的查询用词和文档用词的相关度,针对每个查询词,选出与该词最为相关的k个文档用词发往目录节点.
方法如下:I)叶节点利用本地维护的历史查询记录建立查询用词和文档用词的关联关系,查询用词和文档用词的连接权重表示两者的相关程度,权重可以根据式(4)计算得出;II)对于本次查询叶节点下载的文档中没有"retrieval"标识的文档,记经过方法(3)处理后的文档所包含的词集为download_word.
对于查询用词A,根据式(4)计算P(WB|WA)(B∈download_word),据此选取k个与A最为相关的文档用词,记为wordA,k;III)计算wordAll,k=∪A∈Q(wordA,k),将wordAll,k发往目录节点.
然而,由于受到计算力等方面的限制,方法(4)对于弱Peer节点而言并不适用,该类节点通常不往目录节点发送任何查询记录.
如图3所示,D是目录节点,由于C是弱节点,因此C不往目录节点D发送任何查询记录,查询记录的发送由叶节点F和G承担.
.
.
.
0.
40.
50.
50.
30.
350.
40.
60.
50.
52CDEFG0.
5.
.
.
.
.
.
.
.
.
0.
35DocumentstermsQuerytermsDocumentstermsQuerytermsFig.
3Sendingofquerynotes图3查询记录的发送综上,每次查询完成之后,查询发起节点需要考察与所下载文档相关的查询结果是否有"retrieval"标识,然后执行以下步骤:(1)针对没有"retrieval"标识的结果所对应的文档执行方法(3)和(4),即从出现频率大于1的文档用词中选出|wordAll,k|个,连同文档来源节点标识IDi一起发送到相应的目录节点;(2)对于有"retrieval"标识的结果,仅需将结果编号及源节点标识发往目录节点.
目录节点收到该类消息后,通过result_idi确定相应的文档单词.
目录节点收到查询发起点的全部反馈消息后,需要更新目录节点中保存的关联权重.
限于篇幅,这里仅讨论HEM方法.
不妨记pre_word和c_word分别为更新前目录节点保存的文档词集和本次查询记录包含的文档词集,c_file和all_file分别为本次查询记录包含的文档集和更新后目录节点保存的文档集,pre_query和c_query分别为更新前目录节点保存的查询词集和本次查询记录包含的查询词集.
对任意查询用词A与文档用词B而言,记更新前的关联权重为P(WB|WA),更新后的关联权重为P′(WB|WA),则有张骞等:混合P2P环境下有效的查询扩展及其搜索算法787∈∈∈∈∈∈∩∈∈′*′*∈∈′*=′∑∑∈∈otherwise),,,()_(and__if,),,()__and__(or)__and__(if,0)__(and)__(if,)()()()()|()__(and)__(if,)()()|()|(__filealldifilecdiAAABABABiidBAfquerycAwordprewordcBdBAfquerycquerypreAwordprewordcBqueryprequerycAwordcwordpreBquerycquerypreAwordcwordpreBWfWfDcountDcountWWPquerycquerypreAwordcwordpreBDcountDcountWWPWWP)((7)其中,)(),()()()()(),,(,,AiAiiAiiBiiWfdWfDcountdcountdsizeFDdsizeFDdBAf***=.
f(WA)和f′(WA)分别为查询用词A更新前后出现在历史记录中的频率,count(D)和count(D′)分别为更新前后历史记录中包含的文档数目.
显然,LEM和HEM方法在目录节点上聚集众多叶节点的历史查询记录并执行查询扩展,使得各个叶节点的查询信息得以共享,避免了单个节点因为自身信息的有限性而可能导致查询扩展的低效性.
6基于查询扩展的搜索算法P2P环境下的搜索算法已成为研究热点之一[11,12].
限于篇幅,我们在此仅讨论与本文相关的混合P2P环境下的搜索算法.
混合P2P环境下的搜索算法主要有以下几类:(1)基于文件名的搜索.
叶节点将所包含文档名字的hashing发送到与之连接的目录节点,查询到来时,目录节点根据保存的文件名信息将查询路由到满足条件的叶节点上,而目录节点之间的路由则采用泛洪(flooding)的方式,如Gnutella0.
6[12]采用的方法.
(2)基于文档词集的搜索.
文档词集指的是叶节点所包含的全部文档用词集合.
叶节点将自身的文档词集摘要发往与之连接的目录节点,查询到来时,目录节点通过判断查询用词与摘要的匹配程度来选择到叶节点的路由.
目录节点之间的路由仍然采用泛洪的方式.
(3)基于内容的搜索.
在该类方法中,叶节点的路由选择采用了修改后的K-Ldivergence[11]资源选择算法,该算法需要叶节点将自身包含的文档用词及其频率信息发送到目录节点.
目录节点之间的路由选择则通过观察邻近目录节点对以往查询的响应,计算新查询与历史查询的相似程度来判定.
文献[11]是这类算法的典型代表.
这里,我们提出了一种新的混合P2P环境下的搜索算法,称为SE(searchbasedonqueryexpansion)算法.
SE算法利用了历史查询记录信息,查询记录不仅蕴涵了查询与文档的关联关系,也包含了查询、文档与源Peer的关联关系,因而可以建立查询与Peer的直接关联.
这种关联为路由查询提供了一定的指引信息,如图4所示.
Fig.
4Correlationbetweenquerytermsandpeernodes0.
40.
50.
50.
60.
30.
50.
550.
30.
50.
60.
60.
40.
350.
360.
30.
6.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
PeernodesPeernodesNotesQuerytermsQuerytermsDownloaddocuments.
.
.
0.
7图4查询用词空间与Peer节点的关联关系SE算法实质上是计算扩展后的查询与Peer节点的相关度,选择相关度高的节点转发查询.
由图4可知,若查询与节点的相关度很高,则意味着该节点包含的文档与查询相关度很高,因而能为路由查询提供指引.
相关度可以转化为查询用词和节点间的关联权重.
在目录节点IDj上,对其历史查询记录中包含的任意查询用词ti和节点IDj,k,记其关联权重为Weighti,j,k.
可以通过查询用词和节点在历史记录中共同出现的频率来估算.
jikiikjikikjiITtfIDtfWeight,,,,,,)(),(**=(8)788JournalofSoftware软件学报Vol.
17,No.
4,April2006.
)0.
1log()/)5.
0log((,)_/(,,,,++=+=jijjikkikikinnfnIqwavgqwqfqfT其中,fi,k(ti,IDj,k)是查询用词ti与节点IDj,k同时出现的历史记录数目;f(ti)是ti出现的历史记录数目;qfi,k是ti在IDj,k的文档(这里以历史记录中IDj,k对应的文档用词近似)用词中出现的频率;qwk是IDj,k包含的总文档用词数目;avg_qw是历史记录中全部节点包含的平均文档用词数目;Ii,j类似于反排文档索引,其中nfi是历史记录中包含ti的节点数目;nj是历史记录中总的节点数目.
fi,k(ti,IDj,k)的含义是:若ti与IDj,k以较高的频率共同出现,则ti与IDj,k高度相关;Ti,k和Ii,j的含义是:ti相对于IDj,k的权重与ti在IDj,k包含的文档用词中出现的频率成正比,与包含ti的节点数目成反比.
计算出关联权重之后,可以进一步计算查询Q与节点IDj,k的相似度成绩score(Q,IDj,k):∑==||1,,,||1),(QikjikjWeightQIDQscore(9)综上,当查询Q到来时,目录节点执行SE算法,步骤如下:(1)首先,采用LEM或HEM方法将Q扩展为新查询Q′;(2)然后,依据式(9)计算各个邻居节点与Q′的相似度成绩,选取K个与查询最为相关(成绩最高的)的邻居节点转发查询.
需要着重指出的是,SE算法集中于目录节点间的路由,而目录节点之间的组织形式完全是无结构的,这种组织形式与无结构P2P网络的主要区别在于目录节点本身通常并不共享文档.
即使将目录节点所保存的叶节点文档信息视为其本身共享的文档,但这些文档信息量通常较大,因而导致较高的通信和维护代价,使得无结构P2P网络中广泛存在的基于节点内容的启发式路由算法并不适用于目录节点间的路由.
文献[13]提出了基于查询聚集的无结构P2P网络路由算法,但这类算法与上述文献[11]中的目录节点之间的路由算法本质上是一致的,即路由决策的依据完全来源于历史查询文本信息.
与其不同的是,SE算法是基于历史查询记录的,这里所说的历史查询记录既包含了历史查询文本信息,也包含了下载的文档信息;另外,SE算法采用扩展后的查询参与路由决策,因而相对于上述算法,SE算法能够更好地为路由查询提供指引.
值得一提的是,P2P网络的一个重要特性就是节点可以自由加入和退出网络.
特别地,由于混合P2P网络采用的是层次化的架构,因而频繁加入和退出的节点通常是叶节点,目录节点一般相对稳定.
而且,叶节点的加入和退出不会对目录节点上的历史查询记录产生影响,即使某一目录节点所属的全部能够发送查询记录的叶节点同时退出,其他弱Peer节点仍然可以通过目录节点进行查询扩展;若是目录节点退出,其所属的叶节点也可以连接到新的目录节点.
因此,节点的自由加入和退出对本文提出的查询扩展及其搜索算法影响不大.
另外,叶节点可以根据自身的能力(如接入带宽等)设定每次返回查询结果的最大数目,而目录节点则可以根据叶节点设定的最大数目逐步返回查询结果.
这里,目录节点起到一个缓存的作用.
7性能分析7.
1存储代价这里考虑目录节点和叶节点上存储历史记录的代价.
由第5节可知,叶节点利用查询记录构建查询用词、文档用词和源节点的关联关系.
假定记录中包含Nquery-term个查询用词、Ndoc-term个文档用词和Nfile个文档,这些文档来源于Ncount个节点.
同时,设每个文档用词和查询用词是字符,占1个字节,则叶节点所需的存储空间为STORAGEleaf-node=Ndoc-term+Nquery-term+Ndoc-term*Nquery-term*8+(Ndoc-term+Nquery-term)*Nfile*8+Nfile*8+Ncount*8,其中:每对查询用词和文档用词对应一个关联权重,为double型,占8个字节;每个查询用词或文档用词在文档中出现的频率为double型,占8个字节;文档大小及文档来源节点标识也为double型,各占8个字节.
相对于文档用词而言,查询用词、文档大小和节点标识占用的存储空间可以忽略不计,因此有STORAGEleaf-node≈Ndoc-term*(Nfile+Nquery-term)*8.
对于目录节点,,假定其叶节点数目为Nneighbor,由于计算力等方面的差异,并非全部叶节点都可以构建上述张骞等:混合P2P环境下有效的查询扩展及其搜索算法789关联关系,由此易得STORAGEsuper-node≤Nneighbor*STORAGEleaf-node+Nneighbor*Nquery-term*Nneighbor*Ncount*8.
考虑SE算法,其中每对查询用词和节点对应一个关联权重,为double型,占8字节.
由上述分析可知:Nneighbor一般不大,随着查询数目的增多,Ndoc-term,Nquery-term和Ncount逐渐变大.
我们可以规定Ndoc-term,Nquery-term和Ncount的最大数目,并采用LRU(leastrecentlyused)策略进行淘汰,保证历史记录中存储常用的查询用词.
7.
2网络通信代价通信代价用需要传输的字节数来衡量.
这里,我们仅讨论查询结果返回之后,由叶节点向目录节点发送消息所产生的通信开销.
假定扩展后的查询包含Nquery个查询用词,下载的文档数目为Ndoc,这些文档来源于Nnode个节点,根据第5节的讨论,针对每个查询用词A选取k个最相关的文档用词,记为wordA,k,即wordAll,k=∪A∈Q(wordA,k),同时假定每个文档用词占用1字节.
于是有communication≈|wordAll,k|+Ndoc*4+Nnode*8≈Nquery*k+Ndoc*4+Nnode*8,其中,目录节点为每个查询结果做的编号为int型,占4个字节;节点标识为double型,占8字节.
因为用户提交的查询多为1~3个单词的短查询,且有研究表明[8],向原查询加入30个扩展词时查询性能达到最高,由此可得,Nquery*k≈30*30=900;communication≈900+Ndoc*4+Nnode*8.
显然,下载文档越多,通信代价就越高.
而对于弱节点而言,这类节点通常不保存查询记录,因而这类节点发送消息的开销为0.
7.
3查询响应时间查询响应时间包括网络延迟和访问节点的查询处理时间.
查询处理时间又进一步分为Peer选择的时间、本地查询的时间、结果合并的时间和查询扩展的时间.
在此,仅讨论在目录节点上进行查询扩展所需的时间及Peer选择的时间.
假定目录节点保存的文档用词数目为Nterm,因为原查询多为短查询,因而根据式(3)和式(6)易得查询扩展的时间复杂度为O(Nterm).
假定目录节点保存的邻居节点数目为Nneighbor,扩展后的查询长度为Lenquery,由式(9)可得,Peer选择的时间复杂度为O(Nneighbor*Lenquery),其中查询长度一般为30左右.
因此,总的时间复杂度为O(30*Nneighbor)+O(Nterm).
随着查询记录的增加,时间复杂度也随之增大.
可以规定最大的文档单词数目和邻居节点数目,使用LRU策略淘汰不经常使用的文档单词,并计算每个邻居节点被选择转发的频率,淘汰转发频率低的节点.
7.
4更新代价查询完成之后,查询发起节点和目录节点需要对各自保存的查询记录进行更新.
限于篇幅,这里仅讨论目录节点上的更新代价.
以HEM方法为例,由式(7)得到更新代价为UpdateCostsupernode=|pre_wordc_word|*|pre_query|+|c_wordpre_word|*|c_query|*|c_file|+|c_word∩pre_word|*|all_file|*|post_query|.
显然,|pre_wordc_word|+|c_word∩pre_word|+|c_wordpre_word|=|post_word|且|C_file|≤|all_file|,因此,UpdateCostsupernode<|post_word|*|all_file|*|post_query|.
随着查询数目的增多,post_query,post_word和all_file都可能逐渐变大.
对于post_query和post_word,可采用LRU策略淘汰历史记录中不常用的查询用词和扩展用词;对于all_file,可规定最大的文档数目Nfile,当超过这个数目时,淘汰文档用词使用频率低的文档.
另外,目录节点的更新可离线计算,并设定更新周期,这可以极大地降低更新的代价.
8实验及分析本节通过一系列实验来验证查询扩展及其路由算法的有效性.
目前,没有标准的文档测试集用于混合P2P环境下查询扩展的测试.
因此,我们单独开发了一个文档测试集,约为2.
5G大小,文档来源于NEUSOFT等计算机类网站,将HTML标题作为文档的名字,并删除文档中诸如a,the,is等出现频率极高的词.
因为网络用户提交的查询多为短查询,因此,我们从文档名中随机提取关键字来构造查询测试集,测试集包含的查询多为23个单词的790JournalofSoftware软件学报Vol.
17,No.
4,April2006短查询,目录节点间的拓扑结构基于Power-Law[14]构造.
测试时,随机选择叶节点发送查询,并假定该叶节点不包含查询对应的文档.
这里,采用精度-查全率(precision-recall)指标评价查询性能,查询精度和查全率定义为∑∑∑∑==avaliablesystemretrievedretrievedqualifiedAnswerAnswercallReAnswerAnswerecisionPr,(10)采用标准的向量空间模型VSM(vectorspacemodel)[15]作为叶节点的检索算法,同时实现了文献[11]中的搜索算法(history_basedsearch,简称HS)作为本文算法的比较.
表1总结了实验参数,表2为查询扩展的测试集.
Table1ParametersofexperimentsTable2Queriesfortest表1实验参数表2测试查询列表ParameterDefaultvalueDescriptionNetworktopologyPower-LawThetopologyofnetworkNetworksize2550150directorynodesand2400leafnodesQueriesnumber8000ThenumberofqueriesQuerysize23AveragetermsnumberfororiginalqueriesTTL5Thetime-to-liveofaquerymessageExpansionterms30ThenumberofexpansiontermsforaquerySelecteddocuments15ThenumberofselecteddocumentsforLEMNumberQuery1Storagetraining2Qualitymanagement3Contentmanagement4Solution5E-Learningbusiness6Networksecurity7Educationforum8Callcenter9Humanresourcemanagement10Digitalmedicine8.
1实验1该实验的目的是检验LEM和HEM查询扩展算法能否提高现有HS搜索算法的性能.
首先执行前4000个查询积累查询记录.
随机选择叶节点发送查询,中间路由的节点依据查询与邻居节点的相似度选择K个节点转发查询;随后,将扩展后的查询应用于HS算法,以观察查询性能的变化.
比较的结果如表3(TTL=5,K=3,querynumber=4000)及图5所示.
Table3Comparisonofqueryefficiency表3查询性能比较PrecisionRecallHSLEM_basedHS(improvement%)HEM_basedHS(improvement%)1055.
5666.
67(+20.
00)71.
42(+28.
55)2045.
4554.
05(+18.
92)58.
82(+29.
42)3041.
6648.
38(+16.
13)50.
84(+22.
04)4033.
6139.
22(+16.
69)41.
67(+23.
98)5026.
4535.
46(+34.
06)35.
21(+33.
12)6020.
0029.
85(+49.
25)28.
30(+41.
50)7015.
5219.
50(+25.
64)20.
95(+34.
99)8012.
2815.
78(+28.
50)17.
05(+38.
84)909.
4712.
89(+36.
11)14.
78(+56.
07)1007.
4010.
91(+47.
43)12.
33(+66.
62)Totalaveraged26.
7433.
27(+29.
27)35.
14(+31.
41)从表3可以看出:在测试数据集上,查询扩展后的HS算法确实获得了比较好的结果,相对于基本的HS算法,基于HEM方法扩展的HS算法在精度方面提高百分比最大可以达到66.
62%,平均为31.
41%;而基于LEM方法扩展的HS算法则在精度方面平均提高了29.
27%.
当7000个查询执行完毕时,查询性能的比较如图6所示.
显然,随着历史记录的积累,查询精度随之会有所提高,查询扩展的优势也越加明显.
这主要是由于历史记录的积累,同样也意味着用户关于查询用词和扩展用词间相关性判断的积累,因而扩展更加有效.
张骞791等:混合P2P环境下有效的查询扩展及其搜索算法HSLEM_basedHSLEM_basedHSHSHEM_basedHSHEM_basedHS00.
10.
20.
30.
40.
50.
60.
70.
80.
900.
10.
20.
30.
40.
50.
60.
70.
80.
9PrecisionPrecisionFig.
5ComparisonofqueryefficiencyFig.
6ComparisonofqueryefficiencyRecall(TTL=5,K=3,querymumber=7000)102030405060708090100Recall(TTL=5,K=3,querymumber=4000)图5查询性能比较图6查询性能比较8.
2实验2该实验对现有HS算法的查询结果、基于HEM方法扩展的SE的结果和基于LEM方法扩展的SE的结果进行了比较(见表4和图7(TTL=5,K=3)).
实验表明:与HS算法相比,基于HEM方法扩展的SE算法在精度方面提高百分比最大可以达到67.
03%,平均为42.
60%.
即使与基于HEM方法扩展的HS算法相比,我们的算法同样获得8.
51%的提高;基于LEM方法扩展的SE算法在精度方面提高的百分比平均为41.
58%,在与基于LEM方法扩展的HS算法的比较中,算法也获得了13.
80%的提高.
在SE算法中,除查询文本信息以外,用户点击下载的文档信息也被作为查询路由的指引,因此算法获得了较好的查询效果.
Table4Comparisonofqueryefficiency表4查询性能比较0LEMbasedSEHEMbasedSEHS0.
10.
20.
30.
40.
50.
60.
7Precision0.
80.
9PrecisionRecallHSLEM_BasedSE(improvement%)HEM_BasedSE(improvement%)1055.
5683.
34(+50.
00)76.
92(+38.
44)2045.
4560.
61(+33.
36)64.
52(+41.
95)3041.
6655.
56(+33.
37)57.
69(+38.
48)4033.
6143.
47(+29.
34)44.
45(+32.
25)5026.
4536.
49(+37.
96)38.
76(+46.
54)6020.
0029.
85(+49.
25)31.
58(+57.
90)7015.
5221.
27(+37.
05)22.
44(+44.
59)8012.
2817.
51(+42.
59)17.
66(+43.
81)909.
4715.
17(+60.
19)15.
02(+58.
61)1007.
4012.
33(+66.
62)12.
36(+67.
03)Totalaveraged26.
7437.
86(+41.
58)38.
13(+42.
60)50K=3)7060809010010203040(TT=5,RecallFig.
7Comparisonofqueryefficiency图7查询性能比较另外,由上述实验可知:HEM方法的查询效果略优于LEM方法,主要是因为LEM方法仅从与查询最相关的N篇文档中选择查询扩展词,这样可能导致部分查询用词与文档用词关联信息的损失.
而HEM方法则从全部的历史查询记录中选择扩展词,因而相对于LEM方法涵盖有更多的关联信息.
然而,由第7.
4节可知:HEM方法的更新代价最大为|post_word|*|all_file|*|post_query|,与文档用词的数目成正比.
而LEM方法的更新主要涉及到N篇最相关文档的重新选择,更新代价增加缓慢,且通常情况下,比HEM方法的代价要小.
8.
3实验3该实验的目的是检验增大K对查询效果的影响.
HS算法和SE算法搜索的范围受到选择节点个数(K)的影响,增大K可以提高查询的效果.
限于篇幅,在此仅列出HS算法和基于HEM方法扩展的SE算法在不同K值下的查询结果.
基于LEM方法的SE算法和HS算法的比较结果与此类似.
实验结果表明:增大K能够提高查询精度,在K=4的情况下(见表5和图8(TTL=5,K=4)),SE算法较HS算法在精度方面最大百分比可达38.
05%,平均为17.
37%;在K=5的情况下(见表6和图9(TTL=5,K=5)),SE算法较HS算法在精度方面最大百分比可达47.
58%,平均为18.
61%.
图10表示了在不同K值下,SE算法和HS算法平均精度的变化.
显然,SE算法的表现明显优于HS算法.
值得一提的是,增大TTL能够取得与增大K类似的效果.
虽然增大K或TTL能够提高查询的效果,但也会影响查询的效率,因为这意味着搜索将访问更多的节点.
因此,一般情况下,K取值为3,TTL为5.
792JournalofSoftware软件学报Vol.
17,No.
4,April2006Table5Comparisonofqueryefficiency(k=4)Table6Comparisonofqueryefficiency(k=5)表5查询性能比较(k=4)表6查询性能比较(k=5)Fig.
8ComparisonofqueryefficiencyFig.
9ComparisonofqueryefficiencyPrecisionRecallHSHEM_basedSE(improvement%)1071.
4283.
33(+16.
68)2068.
9676.
92(+11.
63)3065.
2171.
42(+9.
52)4055.
5566.
67(+20.
02)5039.
3754.
35(+38.
05)Totalaveraged60.
1070.
54(+17.
37)PrecisionRecallHSHEM_basedSE(improvement%)1075.
0090.
91(+21.
21)2071.
4280.
00(+12.
01)3068.
1875.
00(+10.
00)4062.
5067.
79(+8.
47)5041.
3260.
98(+47.
58)Totalaveraged63.
6874.
94(+18.
61)HEM_basedSEHSPrecision10.
40.
50.
60.
70.
80.
91020304050Recall(TTL=5,K=5)0.
30.
40.
50.
60.
70.
80.
91020304050HEM_basedSEHSRecall(TTL=5,K=4)Precision图8查询性能比较图9查询性能比较0.
8AveragePrecisionHEM_basedSEHS0.
70.
60.
50.
40.
32345Fig.
10ChangeofaverageprecisionK(TTL=5)图10不同K值下平均精度的变化8.
4实验4实验的目的是评价不同算法的搜索效率.
取查询访问的节点数(如图11所示)和传递的查询消息数(如图12所示)作为衡量搜索效率的指标.
访问的节点越少,传递的消息数就越少,搜索的效率就越高,付出的代价就越小.
060120180240300360AveragevisitednodesnumberFig.
11ComparisonofaveragevisitednodesnumberFig.
12Comparisonofaveragemessagenumber1020304050HEM_basedSEHSAveragemessagesnumber860113014005032059050203040Recall(TTL=5,K=3)10HEM_basedSEHSRecall(TTL=5,K=3)图11平均访问节点数目的比较图12平均发送消息数目的比较从图11和图12容易看出:获取同等数目的相关结果,SE算法需要访问的节点数和发送消息的数目都明显低于HS算法;相关结果获取的数目越多,SE的优势也越加明显.
这主要是因为用户提交的短查询无法提供检索出相关文档的足够信息,而查询扩展弥补了这一缺陷.
基于LEM的SE算法与HS算法的比较结果类似,在此不再详述.
9结论本文讨论了如何在混合P2P环境下进行有效的查询扩展,并在此基础上提出了一种新的混合P2P环境下的搜索算法.
分析和仿真表明,查询扩展及其搜索算法能够提高搜索的效果.
如何聚集相同领域的叶节点,使得目录节点上的查询扩展更具针对性,是我们下一步的研究目标.
张骞等:混合P2P环境下有效的查询扩展及其搜索算法793References:[1]ZhangQ,SunY,LiuZ,ZhangX,WenXZ.
DesignofaP2P-basedgridcontentmanagementarchitecture.
In:IiowJ,ed.
Proc.
ofthe3rdCommunicationNetworksandServicesResearchConf.
NewYork:IEEEPress,2005.
339344.
[2]ClarkeI,SandbergO,WileyB,HongTW.
Freenet:Adistributedanonymousinformationstorageandretrievalsystem.
In:FederrathH,ed.
Proc.
oftheWorkshoponDesignIssuesinAnonymityandUnobservability.
Berlin:Springer-Verlag,2001.
4666.
[3]FurnasGW,LandauerTK,GomezLM,DumaisST.
Thevocabularyprobleminhuman-systemcommunication.
CommunicationsoftheACM,1987,30(1):964971.
[4]JansenBJ,SpinkA,SaracevicT.
Reallife,realusers,andrealneeds:Astudyandanalysisofuserqueriesontheweb.
InformationProcessingandManagement,2000,36(2):207227.
[5]DeerwestrS,DumaiST,FurnasGW,LandauerTK,HarshmanR.
Indexingbylatentsemanticanalysis.
JournaloftheAmericanSocietyforInformationScience,1990,41(6):391407.
[6]SaltonG,BuckleyC.
Improvingretrievalperformancebyrelevancefeedback.
JournaloftheAmericanSocietyforInformationScience,1990,41(4):288297.
[7]BuckleyC,SaltonG,AllanJ,SinghalA.
AutomaticqueryexpansionusingSMART:TREC3.
In:HarmanDK,ed.
Proc.
ofthe3rdTextRetrievalConf.
Gaithersburg:NISTPress,1994.
6980.
[8]XuJX,CroftWB.
Improvingtheeffectivenessofinformationretrievalwithlocalcontextanalysis.
ACMTrans.
onInformationSystems,2000,18(1):79112.
[9]CallanJP,LuZH,CroftWB.
Searchingdistributedcollectionswithinferencenetworks.
In:FoxEA,IngwersenP,FidelR,eds.
Proc.
ofthe18thAnnualInt'lACMSIGIRConf.
onResearchandDevelopmentinInformationRetrieval.
NewYork:ACMPress,1995.
2128.
[10]CuiH,WenJR,NieJY,MaWY.
Queryexpansionbymininguserlogs.
IEEETrans.
onKnowledgeandDataEngineering,2003,15(4):111.
[11]LuJ,CallanJ.
Content-Basedretrievalinhybridpeer-to-peernetworks.
In:FriederO,HammerJ,etal.
eds.
Proc.
ofthe12thInt'lConf.
onInformationandKnowledgeManagement.
NewYork:ACMPress,2003.
199206.
[12]Thegnutellaprotocolspecificationv0.
6.
2005.
http://rfc-gnutella.
sourceforge.
net[13]HeYJ,FengYL,WangS.
Intelligentsearchbasedoncontentofdocumentsinpeer-to-peernetwork.
JournalofComputerResearchAndDevelopment,2004,41(Suppl):112118(inChinesewithEnglishabstract).
[14]PalmerCR,SteffanJG.
Generatingnetworktopologiesthatobeypowerlaws.
In:GavalasD,GreenwoodD,etal.
eds.
Proc.
oftheIEEEGlobalTelecommunicationConf.
(GLOBECOM2000).
SanFrancisco:IEEEPress,2000.
434438.
[15]WangZW,WongSKM,YaoYY.
Ananalysisofvectorspacemodelsbasedoncomputationalgeometry.
In:BelkinNJ,IngwersenP,etal.
eds.
Proc.
ofthe15thAnnualInt'lACMSIGIRConf.
onResearchandDevelopmentinInformationRetrieval.
NewYork:ACMPress,1992.
152160.
附中文参考文献:[13]何盈捷,冯月利,王珊.
Peer-to-Peer环境下基于内容的智能搜索.
计算机研究与发展.
2004,41(增刊):112118.
张骞(1979-),男,山东金乡人,博士生,主要研究领域为数据管理与P2P计算.
孙雨(1975-),男,博士生,主要研究领域为数据管理与P2P计算.
张霞(1965-),女,博士,教授,CCF高级会员,主要研究领域为P2P数据管理,数据库技术.
文学志(1970-),男,博士生,主要研究领域为网络安全.
刘积仁(1955),男,博士,博士生导师,主要研究领域为计算机网络技术.
刘铮(1979-),女,硕士,主要研究领域为数据管理.