一种P2P系统节点聚类及信息检索算法
开篇：润墨网以专业的文秘视角，为您筛选了一篇一种P2P系统节点聚类及信息检索算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：提出了一种节点聚类及信息检索算法――NCSearch。NCSearch利用Hilbert曲线的局部性特征保持能力,将有相似内容的节点聚类，形成若干个簇。搜索算法能快速定位到与查询最相关的簇，然后在簇内洪泛查找，返回的结果按相关度排序。模拟测试表明,NCSearch稳定高效,相比传统算法在搜索效率方面有明显提高。
关键词：p2p；局部性；聚类；Hilbert空间填充曲线；向量空间模型
中图分类号：TP393文献标识码：A
文章编号：1001-9081(2007)04-0821-04
0引言
Peer―to―Peer(P2P)系统以其自治性、可靠性、可伸缩性和低成本性等优点,成为文件共享的理想平台。然而,P2P系统也有其自身的一些缺点,比如参与节点的数目庞大,动态性强,缺乏中央的控制机制以及难以获得全局信息。这给文件共享带来了不小的困难,特别地,在P2P系统中查找相关文档(信息检索)的性能(查全率、查准率和响应时间)受到了很大的影响.在P2P系统中采用基于节点聚类的信息检索方法正受到日益广泛的关注[1],节点簇的形成给P2P环境下进行信息检索带来了两个重要的好处:1）簇的成员能在簇中找到更有价值的文档;2）大多数的搜索工作可以被限定在簇中完成。这样,大大降低了网络开销.
本文提出了一种有效的节点聚类和信息检索方案――NCSearch。NCSearch利用Hilbert[2，3]空间填充曲线的内容局部性特征保持能力，将具有相似内容的节点聚集成簇，搜索算法首先快速定位到与查询向量最相关的若干个簇，然后依次在这些簇内洪泛查找。模拟测试表明，NCSearch在搜索效率上较Gnutell[4]有明显的改进。
1相关工作
1.1文档的特征向量表示
在经典的信息获取模型中，一个文档可以标识成一个具有字典维数的特征词向量(一个字典是一个文档集中所有唯一特征词列表)。设P2P网络系统中所有节点集合为
1.2节点向量和簇向量
为了在搜索算法中计算查询与节点，查询与簇之间的相关度，进一步提出了节点向量和簇向量的概念。
1.3Hilbert空间填充曲线
2系统设计
2.1节点聚类模型
我们的设计考虑了节点能力异构性，按节点的能力将节点分成两类：超级节点和普通节点,为了方便描述，首先给出一组定义。
定义1簇中心节点,指初始化并维护簇的超级节点。
定义2簇内节点,就是指某个簇中心节点的所有孩子节点。
2.2节点加入、离开算法
普通节点RP的加入步骤:1）将其HibertID作为key在SuperNodeDHT中路由查找到与自己具有最小Djoin
值的超级节点SP;2）与SP建立连接，并将节点向量上传给SP，SP给RP分配最多K个簇内距离最近的节点作为簇内邻居节点。
超级节点SP的加入步骤：1）调用Chord的加入算法加入到SuperNodeDHT中，并初始化新簇；2）通知环中的前驱和后继超级节点，前驱和后继超级节点各自计算其簇内节点与SP的Djoin值,若Djoin小于簇内节点到自己的距离，则将这些簇内节点转移至SP所维护的簇中；3）SP然后执行与普通节点相同的加入步骤。
如果是普通节点离开，离开时只需通知超级节点；如果是超级节点离开，则还需将其维护的簇内节点转移至前驱或者后继节点。节点的加入、离开算法的伪代码如下所示。
簇内节点的连接根据Hilbert数字距离的远近建立，实际上通过簇中心节点计算节点向量的相关度，可以获得更为准确的语义邻居。但是这增加了簇中心节点的计算负荷，尤其当更新周期较短时，簇中心节点需要频繁计算节点向量的相关度，导致负载过重。将这两种不同的连接方式称作HLink和SLink。
2.3资源定位过程描述
为了控制簇内洪泛所引起的消息冗余，查询发起节点给查询分配一个唯一的标识符GUID，在洪泛过程中，一旦节点接收到已经访问过该节点的带相同GUID的查询，则将其丢弃掉。
2.4节点向量与簇向量的更新策略
节点的文档内容集合经常会发生改变，因此它的节点向量也会发生变化，节点需要周期性地计算其节点向量的HilbertID以及与簇中心节点的距离，如果发现与中心节点距离已超出某一阈值，则重新执行一次节点加入算法，加入到正确的簇中;否则，节点会将节点向量上传给簇中心节点，为了减少带宽的消耗，仅传送节点向量的“ultradelta”变化量。
簇内节点的节点向量变化，则簇向量也会发生变化，超级节点周期性地计算簇向量，并将簇向量的“ultradelta”变化量在SuperNodeDHT环中广播。广播采用文献[7]提出的有效Chord广播算法,该算法保证环内所有节点只收到消息一次，没有冗余信息产生，如环内超级节点数为N，则总共产生N-1条消息。
2.5故障容忍与语义邻居维持
在P2P这样的高度动态环境中，为了保证在簇中心节点发生故障情况下，其簇内节点仍能找到相应的簇加入，采用了一种“LazyRepair”的方式。由于簇内节点CP要周期性向簇中心节点SP发送节点向量的变化量消息，因此可以在该消息上附加一个“Keepalive”消息，SP必须回复一个“Keepalive”消息，并重新为CP分配K个簇内距离最近的邻居节点，将这些节点的HilbertID及IP地址附加在回复消息上返回给CP，收到消息的CP会重新建立与新的K个邻居节点的连接；如果CP没有收到SP返回的“Keepalive”消息，则认为SP已失效，并重新执行一次节点加入算法，加入到正确的簇中。同样，SP如果在周期T内未收到CP发来的消息，则它认为该节点已失效，因此会移去所维护的CP的节点向量及其他相关信息。通过这种方式，节点总能加入离自己最近的簇，并获得与自己簇内距离最近的K个邻居节点的连接。
3实验仿真
3.1实验设置
模拟实验在一台配置为CPUP42.0GHz，内存1GB，操作系统为Windows2000的PC机上进行。模拟程序用Java语言编写,其中NCSearch模拟程序建立在开源模拟器OpenChord的基础上。为了验证本文提出方法的有效性，比较了NCSearch与Gnutella(随机走步)的搜索性能，并且比较了NCSearch采用二种不同策略(HLink和SLink)时的搜索性能。
实验所采用的文档数据来自Reuters[8]，Reuters是广泛用于IR检索领域的文档测试集，其中包含了大量带有作者字段的新闻文档，从Reuters集随机选取了1384个作者的文档，从每个作者的文档中再抽取子集，这样共抽取了24750篇文档构造文档集,这些文档覆盖了经济、体育、战争等多个主题。实验用一个作者模拟一个节点，与该作者有关的文档存放在这个节点。对文档集中的每篇文档进行预处理:保留词干，去除文档中的停用词和高频词汇。然后从预处理过的文档集中选取IDF反转频率最高的100个词条作为特征词，用于构造文档向量。随机选择一个文档，并随机从该文档的特征词向量中抽取3个特征词来构造一个查询，通过这种方式共生成了有50个查询的查询集。为了便于实验，这里假定与一个查询相关的文档是那些包含查询中所有特征词的文档。根据GnutellaProfile,节点按能力划分为1×，10×，100×，1000×，10000×五个等级，各占节点总数的百分比分别为20%，45%，30%，4.9%，0.1%，因此将1000×设为超级节点能力阈值。实验中的部分参数设置见表1。
2)查询处理开销:是指分布式查询过程中路由和处理查询消息的节点数目百分比,为消耗系统资源的决定因素。低的查询处理开销增加了系统的扩展性。
3.2实验结果及分析
图片图3HLink和SLink在不同簇数目下的查全率图2给出了在簇数目为16(即16个超级节点)的条件下查全率随查询处理开销的变化情况。从图2可以看出，在相同查询处理开销情况下下，NCSearch的两种策略均明显优于Gnutella，在查询处理开销50%的情况下，SLink和HLink的查全率较Gnutella均高出35%以上，其中Slink甚至高出近40%。这是因为NCSearch快速定位至与查询最相关的簇，然后将搜索限定在簇范围内，从而在查询处理开销较小的情况下获得了较高的查全率。从图2中还可以看到，SLink的搜索性能略优于HLink,这是因为在SLink中，簇内节点的连接相关度由簇中心节点进行向量相关度计算得出，因此比HLink更准确。
图3(a)和图3(b)分别给出了HLink和SLink在不同簇数目条件下的查全率随查询处理开销的变化情况。从图3中可以看出，簇数越高，获得的簇的粒度越细，因而搜索的效率越高。
4结语
本文提出了一种有效的P2P系统节点聚类及信息检索算法，主要目标是提高P2P信息检索的效率。通过利用Hilbert空间填充曲线的局部位置特征保持能力快速地将节点聚类成若干个簇，查询能快速定位至与查询最相关的若干个簇，并在簇内进行洪泛搜索。模拟测试表明系统是有效的，但该算法的有效性依赖于节点向量及簇向量的及时更新，更新周期太长会影响搜索质量和效率，太短会加重系统节点的负担，因此更新周期的合理设定是下一步需要研究的问题。此外，引入有效的向量降维机制也是我们下一步研究的目标。
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。