利用层次模型实现P2P网络的全文检索

利用层次模型实现P2P网络的全文检索基金项目：国家自然科学基金（60003004） 周晋，博士生，研究方向为P2P搜索技术和网络信息检索。李衍达，教授，博士生导师，中国科学院院士，研究方向为网络信息服务，生物信息学，智能信号处理等。周晋 李衍达（清华大学 自动化系，北京 100084）摘 要：本文的研究对象是P2P搜索问题。P2P搜索算法的理想目标是：一方面能够达到IR（Information Retrieval）算法的搜索质量，另一方面能够保证搜索的可扩展性。然而，已有研究提出的搜索算法尚不能同时满足这两个条件，为此，本文从层次聚类的思路提出一种新的DHC算法。其主要过程是：首先将共享文件转化成向量样本，然后增量式地向层次树中添加样本，样本按照一定要求放置于合适的位置上。在物理层面上，层次树的节点分置于各个servent，通过servent通讯实现层次树的调整。搜索时，query发起节点首先路由到层次树的根节点，从根节点出发向下逐层搜索，通过比较query与各个下层节点的距离，选出合适的分支继续搜索。在层次树中，叶节点代表样本，当搜索到达叶节点时，满足要求的样本将被发送回初始节点。理论分析和初步的仿真试验表明，DHC算法具有较高的查全率，其搜索深度和更新代价与servent总数的对数成正比。由此可得，基于层次聚类的DHC算法既能达到IR算法的搜索质量，又具有搜索可扩展性，是一种有效的P2P搜索算法。关键词：P2P搜索；可扩展性；分布式；层次聚类；内容索引中图分类号：TP393Using hierarchical model to harness full-text retrieval in peer-to-peer networkZHOU Jin, LI Yanda(Department of Automation, Tsinghua University, Beijing 100084, China)Abstract: Ideal content-based routing algorithm should not only provide IR algorithms effectiveness, but guarantee routings scalability. However, former works did not really achieve both aims. In this paper, we present a novel method named Distributed Hierarchical Clustering to address it. Firstly, files in vector-format are placed to appropriate position in Hierarchical Clustering Tree (HC-Tree). In physical network, HC-Tree nodes may be placed on different servents, and clustering is established by servents communicating. Working in a top-down fashion, a query will be sent from root to relevant sub-nodes. When it reaches leaf nodes which are responsible for files, routing is terminated. The physical addresses of those relevant files will be returned to original node. Results from theoretical analysis and simulations show that, under preservation of a stable recall, DHC is incrementally scalable, with lookup costs scaling logarithmically with the number of servents. In conclusion, DHC is an efficient p2p routing algorithm.Key words: peer-to-peer routing, scalability, distributed, hierarchical clustering, content-based1简介近来，Peer-to-peer系统（简称P2P系统）在文件共享和信息搜索等方面得到了越来越多的应用，Morpheus1的系统报告指出：截止2001年10月26日，用户数量超过470,000位，共享文件总量约360TeraBytes。P2P系统是由一组地位相等的节点构成，节点间可以直接通讯，无需第三方参与。与C/S结构相比，P2P结构可容纳大规模数量的节点，此外，它还具有网络负载平衡、实时性搜索、容错性强等特点。P2P搜索是决定系统性能的首要因素，主要包括两种方式：集中式搜索和分布式搜索，分别对应集中式索引和分布式索引。相比集中式，分布式搜索具有实时搜索、分布处理和平衡网络负载等优势，虽然目前存在搜索时间长、通讯量大等弊端，但能够利用网络整体资源的固有特点仍使它成为了极具潜力的研究问题之一。分布式算法需要满足的一个关键条件是：保证搜索的可扩展性(Scalability)。可扩展性算法应具备的基本条件有（设N为系统节点总数）：1) 时间复杂度与N保持非指数关系。搜索时间应一直保持在可接受范围内，分布式算法的搜索时间与搜索深度成正比；2) 搜索质量不能明显降低；3) 节点索引的存储容量应避免超过用户限定范围。目前被广泛使用的两个系统Gnutella2、Freenet3分别采用了宽度优先(BFS)和深度优先(DFS)搜索方式，两种搜索算法虽然鲁棒性强，但运行效率很低，前者的扩散搜索导致消息呈指数规模增加，后者的回溯搜索导致等待时间过长。Tapestry4 、Pastry5、CAN6和Chord7通过严格控制网络拓扑和文件存放位置，能有效地检索到结果，同时保证搜索步数在O(logN)的范围内，实现了可扩展性搜索，但是，由于搜索算法对节点的限制条件过多，它们更适合运行于公司的内部网络，此外，它们更大的一个局限在于：搜索算法建立在DHTs（分布式哈希表，Distributed Hash Tables）索引上，约束了搜索质量的提高。在P2P系统中，DHTs索引和内容索引是主要的两类索引结构。通常，DHTs是利用哈希函数将文件名映射为key，索引记录形如<key, file_pointer>，搜索工作转变成为key查询，尽管许多DHTs算法具有很强的key查询能力，但是缺乏针对文件内容的查询能力，且无法区分返回结果的优劣程度。相比而言，内容索引在提高搜索质量方面更具优势，查询结果更全面、准确，可按相似度排序，加快用户的检索过程。随着P2P服务的深入发展，用户将对搜索质量提出更高的要求，故我们将研究焦点聚集在针对内容索引的搜索问题上。构建内容索引需要从文件中抽取出加权的关键词向量，而文档8和附带meta-data的多媒体文件都适用于向量抽取操作，为了适应分布式环境，对关键词向量可进行压缩变换，过程是：首先，用索引程序9文件中提取出重要的关键词，组成关键词列表T，然后，通过哈希函数H将T转换成Bloom Filter10的布尔向量V，即向量的每一维非0即1。V的长度为L，最初为零向量，H函数的值域范围为1,L，T到V的转换原则是：若T中存在关键词t，对应地，V的H(t)位的值设为1。判断query与V的相似性时，对于query中的关键词q，计算H(q)，若V的H(q)位为1，表明V中存在q，匹配的q越多，query与V的相似度越高。Bloom Filter方法可以保证搜索全面性，但是不能保证100%准确，这是因为哈希函数可能出现多对一映射。解决方式可以是增加V的长度L，或者并行采用多个哈希函数11。在下文中，我们也称文件向量和Bloom Filter向量为样本。在解决搜索可扩展性问题上，内容索引与DHTs索引所面临的问题存在着本质差别。DHTs在搜索之前已经明确了搜索目标特定的key，而内容索引在搜索之前无法确定搜索目标，需要通过计算相似度来选出匹配程度最大的那些文件。可以说，内容索引无法建立出一个类似于key空间4, 5, 6, 7的有序搜索结构，如何保证内容索引的搜索可扩展性便成为一个挑战性问题。文献12的启发式算法和文献13的聚类算法只是在一定程度上减少搜索步数，并没有解决搜索的可扩展性问题。本文试图通过聚类方式来解决内容索引的搜索可扩展性问题，我们提出了一种分布式的层次聚类算法，利用聚类层次树作为搜索线索，同时，层次树的有限层数保证了搜索的可扩展性。文章结构安排如下：第2节分析了P2P系统中已有聚类算法；第3节具体介绍了分布式层次聚类算法；第4节对层次聚类算法进行了性能评价；最后，在第5节给出结论，指出未来研究工作。2相关工作本文的研究目标是通过聚类方式来解决内容索引的搜索可扩展性问题。在P2P系统中，聚类的本质就是为相似内容建立联系，这样有两方面的优点：1)缩短Hops；2)提高Hits。对于拓扑结构和文件存放位置自由的系统，如：Gnutella、Freenet等，在不影响原有协议的基础上，聚类算法可以对搜索性能有所提高。Ramanathan M.K.等14将邻居分为直接邻居和间接邻居（邻居的邻居），选择以往表现好的节点作为直接邻居。所谓“表现好”指的是能以较短的路径长度，带来较多的返回结果。经过一段时期的调整后，兴趣相近的节点之间便会建立起直接连接。Ng Cheuk-Hang等13设计的聚类算法是应用于图像P2P检索系统的。首先，将每个节点上的图片转化成向量，这样，通过计算向量相似度便可以判断两个文件的相似程度；对于某节点，考察它的邻居上是否存有与本地文件相似的文件，若有，则在两个节点间建立一条attractive link；对每个节点进行该操作，存有相似文件的节点便通过attractive link聚到一起。搜索时，一旦query在某节点找到匹配文件，便可以通过attractive link找到该类的其他文件。上述两种聚类算法存在着共同的不足：无法保证搜索可扩展性。两种算法都只能在找到至少一个结果之后，才能发挥聚类的优势。换句话说，在没找到类别的成员之前，搜索仍然像Gnutella一样，属于盲目搜索。因而，随着节点数量的增加，两种算法仍无法有效控制消息数量和路径长度。本文从模式识别中的层次聚类算法(HC, Hierarchical Clustering)15受到启发，提出一种新的P2P环境下的聚类算法分布式层次聚类算法(DHC, Distributed Hierarchical Clustering)，以达到有效控制搜索消息数量和路径长度的目的。图1 聚类层次树HC算法可以建立起一棵不同层次不同粒度的层次树。如图1，层次树是一棵倒置的树，根节点位于最顶端，叶节点位于末端，每一个代表一个样本。从上到下，每一个节点代表具体层次上的一个分类，类越分越细，所包含的样本越来越少。相比其他聚类方法，层次树起到了以不同相似度尺度对样本进行聚类的效果。同时，它的分层结构具有良好的可搜索性，对于给定的目标，从根节点出发，逐层比较目标与节点的相似程度，选择有可能的分支进行深入搜索，避免了与无关样本的比对操作。HC算法需要运行在一台计算机上，而DHC算法的目标是在分布式环境下建立层次树，为分布式搜索提供线索。在理论上，若样本总数为M，层次树的分支数为B，则树的级数为，则从根节点出发的搜索深度最大为。由于计算机节点上的样本数有限，故可近似认为样本总数M与节点总数N成比例，因而，搜索深度的期望值为。所以，在理论上讲，DHC是一种具有可扩展性的搜索算法。为避免混淆，下文称层次树中的聚类节点为节点，称物理网络中的计算机节点为servent。3 DHC算法在P2P系统的动态环境中，servent流动频繁，共享文件时常变换，因此，我们只能采用增量式算法(IHC, Incremental Hierarchical Clustering)对随时加入的样本进行聚类。IHC算法面临的主要困难是对样本输入顺序敏感的问题，因为如果算法对输入顺序敏感，也就说样本的位置可能因加入顺序不同而不同，搜索准确性当然难以保证。为克服输入顺序敏感的问题，Widyantoro,D等人提出一种新的IHC算法16（记为Widyantoro算法），算法要求在聚类过程中始终保持两个性质：均匀性和单调性，验证表明IHC算法对输入顺序不敏感，DHC算法在构建层次树时借用了Widyantoro算法的思想。在物理实施上，DHC算法将节点分散放置在各个servent上，通过与相关servent交流，增量式地构建层次树，分布式地完成搜索任务。3.1 构建层次树为了克服输入顺序敏感性问题，在增量聚类过程中始终要保持两条性质：均匀性和单调性16。均匀性规范了类内样本之间的距离要求，详见定义1；单调性是指从根节点到叶节点，类内距离的均值递减，更形象地说就是节点所包含的子节点的密度逐渐增大。在介绍构建过程前，我们先给出DHC算法涉及到的一组定义。定义1. 均匀性节点A的类内距离表示为，对于给定的下限函数和上限函数，当且仅当，满足时，称该类满足均匀性。定义2. 类别特征节点A的类别特征表示为，其中均值向量，方差向量。设节点A含有K个子节点A1,A2,AK，它们的均值向量为，i=1K。均值和方差的第j维分别为：, j=1D(1), j=1D(2)类别特征用来描述类的整体特征，它表示类在向量空间中的重心位置和成员的紧密程度。定义3. 节点距离节点A和B的节点距离（后简称距离）为：(3)我们认为：两个节点的均值向量越接近，则距离越近；内部成员的紧密程度，反映了用衡量节点距离的准确性。两个节点距离直接代表了二者的相似度，节点距离越小，相似度越大。定义4. 加入距离加入距离din(B,A)是B到A的所有子节点的最小距离。在聚类过程中，常常会遇到节点B加入另一个节点A的情况，加入距离用来表征B与A的子节点的距离远近程度。如果din(B,A) > A.UL，表明B不属于A类；如果din(B,A) A.UL，表明B属于A类(包括其子类)，即B应作为A的下级节点。注意：加入距离不具有交换性。为了完成构建和搜索层次树的任务，DHC算法的节点需要记录一系列必要信息。首先要记录的是本类的类别特征和类内距离；其次，在选择搜索方向时，需要知道当前节点的子节点的情况，所以要记录直属子节点的类别特征与容量；另外，由于分布式存储节点的缘故，构建和搜索要求节点之间能够相互通讯，所以每个节点还要记录父节点和子节点的指针，即它们所处servent的地址。此外，对于叶节点而言，还应存储源文件的servent地址。表3-1给出了节点的全部聚类信息。表1 节点A的聚类信息符号含义Parent*父节点指针（根节点此项为空）类别特征K节点容量，即A所属的子节点的数量<Childi*, Cati, ki>, i=1,K子节点元组：子节点指针、子节点类别特征和子节点容量（叶节点此项为空）类内距离，其中，di表示第i个子节点与其他兄弟节点的最近距离，通过创建类的最小生成树的方法可以得到di。和分别是NDP的均值和标准差（叶节点此项为空）Source源文件的servent地址，包括IP地址和端口（非叶节点此项为空）*注：节点指针的详细结构为<IP Address, Port, Node ID>，IP Address和Port分别为存放节点的servent的IP地址和端口，Node ID是用来标识节点的全局唯一的16-byte字符串。构建层次树主要包括加入样本和删除样本两种操作。最初，系统创建出内容为空的根节点，节点聚类信息见表1。然后逐一地将发现到的servent的样本加入层次树，发现servent的方法同Gnutella，这里不再赘述。加入样本需要两个步骤：1) 新样本的插入位置的定位Locating（算法A）；2) 新样本插入后，层次树的调整Hierarchy Restructuring（算法B）。算法A比对新样本与当前节点的加入距离，根据比对结果，选择不同分支：a)继续考察父节点，b)加入当前节点，c)插入新层次，d)继续考察距离最近的子节点。在算法B的Hierarchy Restructuring过程中，可能会出现两种情况：1) 当前节点的兄弟节点间的层次关系发生变化，此时，算法C可以将它们的同级关系变为父子关系；2) 当前节点需要调整子节点集合，经过算法D的合并与分割操作，重新安排子节点的层次，以保证当前节点的均匀性。若某次搜索后，发现叶节点A的源文件所在servent（Source）与系统失去连接，需要立即把A从层次树中删除掉。与加入相比，删除免去了样本定位的过程，只需直接通知存储A的所有servent（包括存储备份节点的servent，备份节点的概念见3.2节）删除A即可。然后，同样调用Hierarchy Restructuring，调整牵涉到的其他节点。下面给出算法AD的流程或伪码。算法A Locating(1) 设当前节点为N，如果N为叶节点，则找到它的父节点作为当前节点，否则分情况执行下列步骤：a) 若din(NJ,N) > N.UL，则令NßN.Parent，跳转(1)；b) 若N.LL din(NJ,N) N.UL，则执行操作INS_NODE(N,NJ)（见图2(a)），过程结束；c) 若din(NJ,N)<N.LL，但存在子节点N.Child，满足din(NJ, N.Child)>N.Child.UL，则执行操作INS_HIERARCHY(NI,NJ) （见图2(b)），其中，NI是与NJ的距离最小且满足前述条件的子节点，过程结束；d) 其他情况，即：din(NJ,N)<N.LL，且N.Child，有din(NJ, N.Child) N.Child.UL，则令NßNI，跳转(1)，其中NI是与NJ的距离最小的子节点。算法B Hierarchy_RestructuringLETN = NJ.Parent;/令N为新节点NJ的插入位置（或已删除节点NJ的父节点）WHILE (N null) LET pParent = N.Parent;/记录当前节点的父节点Recover_Hierarchy(N); /调整N的兄弟节点间的层次，内部过程见算法CHomogeneity_Maintenance(N); /维护N的同质性，内部过程见算法DLET N = pParent;算法C Recover_Hierarchy (N)FOR each NI N.Parent.Child_Set /NI是N的同级兄弟节点FOR each NJ N.Child_Set AND NINJ /NJ是与NI不同的N的兄弟节点IF din(NJ,NI) NI.ULTHEN DEMOTE(NI,NJ);/将NJ降为NI的下级，见图2(c)Recover_Hierarchy (NI);/调整NI子节点的层次关系算法D Homogeneity_Maintenance(N)/合并子节点REPEAT LET (NI,NJ) = Min_Pairs(N);/设NI和NJ是N所有的子节点中距离最近的一对；LETbStop = TRUE;IF d(NI,NJ) < N.LL THEN MERGE(NI,NJ);/见图2(d)bStop = FALSE; UNTIL bStop;/分割当前节点LET (MI,MJ) = Max_Pairs(N); /设MI和MJ是N所有的子节点中距离最远的一对；IF d(MI,MJ) > N.ULTHEN LET (NI, NJ) = SPLIT (N);/见图2(e)CALL Homogeneity_Maintenance (NI);CALL Homogeneity_Maintenance (NJ);INS_NODE(N, NJ) INS_HIERARCHY(NI, NJ) DEMOTE(NI, NJ) MERGE(NI, NJ) (NI, NJ) = SPLIT(N)(a) (b)(c) (d) (e)图2 构建层次树的五种元操作算法AD提到了构建层次树的五种元操作，图3-1给出了它们的逻辑实现。(a)INS_NODE(N, NJ)表示把NJ插入到N的子节点集合中；(b)INS_HIERARCHY(NI, NJ)表示新加节点NJ和N的原有子节点NI重新合并成为一个新的N的子节点；(c)DEMOTE(NI, NJ)表示NI和NJ从兄弟关系变为父子关系；(d)MERGE(NI, NJ)表示NI、NJ合并构成新节点NK；(e)(NI, NJ) = SPLIT(N)表示把N分割成为两个新节点NI和NJ，划分依据是前面提到过的最小生成树，用N的所有子节点创建一棵最小生成树，找出权值最大的边（即算法D中MI和MJ构成的距离最大的边），删除此边，将最小生成树分成两部分，每一部分组成一个新节点。3.2 放置层次树节点(a) 物理网络的消息传递(b) 层次树搜索图3 搜索过程为了实现物理网络的分布式搜索，层次树节点需要分布在各个servent上，图3展示了层次树节点放置在物理网络上的情形，一个servent可以放置多个不同的节点。通过当前节点的Parent和Child指针（见表3-1），可以获知父、子节点所在的servent，并与之通讯。1) 节点放置当系统中尚未建立层次树时，由系统建立根节点，并随机选定R个servent分别放置根节点的R个备份（R为常量）。对于新加入的节点，默认放置在父节点的servent上。2) 节点备份在实际系统中，若某节点被频繁访问，会导致servent负载过重，例如：搜索总是要从根节点开始，根节点的访问量会很大，这时，可以通过节点备份进行分流，达到平衡负载的目的，同时也提高了搜索效率和容错能力。节点备份是将一个节点的全部聚类信息从一个servent复制到其他servent。新建节点自动将被复制R份，通过servent连接分布到其他节点上。当节点更新时，节点与备份节点之间要保持同步。因此，每个节点会保留R个备份节点的servent地址，包括IP和端口。当某节点更新后，立即通知其他备份节点更新，更新信息依次地传递下去，最终保证系统中相同节点内容同步。如果备份节点的访问率过低，servent也可以将其删除或转移到其他servent上。3) 预先本地聚类在实际系统中，为了避免因样本过多而导致分布式聚类任务过重，可以先由servent对本地文件进行聚类，已有的模式识别研究成果提供了多种聚类方法17，在类内，样本的聚集程度可根据整个系统对查准率和消息数量的要求而定。每一类由一个聚类中心所代表，聚类中心是与样本同维的向量，因此，我们也可以在广义上把聚类中心叫做一个样本，原来对样本个体的搜索便转化成对聚类中心的搜索。搜索时，先找出与query相似的聚类中心，再对相应的类内文件深入搜索。预先本地聚类的方式可以有效降低网络负载，加快聚类速度和搜索速度。3.3 搜索策略由于节点可能放置在不同的servent上，因而，层次树搜索要通过servent之间的消息传递来实现。比如，当搜索焦点从一个节点转移到它的父节点时，需要向它的父节点的所在servent发送消息，servent收到消息后，根据搜索策略对指定节点进行计算，然后确定是继续发送消息或是返回搜索结果。搜索过程主要包含两个阶段：1) 找到根节点；2) 从根节点出发，搜索与query距离小于的叶节点，是判定匹配与否的距离阈值。为了标明搜索所处阶段，需在消息中添加一个bit(0/1: root_status/leaf_status)。算法E给出了servent具体的搜索策略。搜索过程与新加样本的定位过程（算法A）有所不同，新加样本NJ若要加入节点N至少要满足加入距离din(NJ,N) N.UL，而对搜索来说，是否沿节点N向下深入搜索，判断标准是d(query, N)。算法E Routing policyIF search = root_status /当前阶段：寻找根节点IF current_node is root node /找到根节点search ß leaf_status;/进入搜索叶节点的阶段Recall this procedure;/重新执行该算法过程ELSE Send query to parent node;/向父节点发送queryELSE IF search = leaf_status/当前阶段：搜索叶节点IF current_node is leaf node AND distance of current_node and query is below Send successful message and results to requesting node;/找到目标，回传结果ELSE Compute distance of all child node of current_node against the query;/计算所有子节点的距离Choose nodes which distance is below, if none is selected, choose the minimal one; /选择距离小于的子节点，若无，则选择距离最小的子节点Send query to selected nodes;/向选中的子节点发送query我们以图3为例来说明搜索过程。最初，servent PD提出查询N8的query。首先寻找根节点，N3发送消息到父节点N1，物理通讯过程即为PD向PB发送query；在PB处，得知N1为根节点，因此可以开始搜索目标叶节点，在N1的子节点中，选择与query最接近的N2，PB向PA发送消息；接下去，query又经过N5（位于PC）到达PF，在PF找到了叶节点N8，且距离小于阈值，成功找到结果。关于搜索深度的控制，DHC与Gnutella有所不同。Gnutella通过存活时间计数器TTL(Time-to-live)来控制搜索深度，随着搜索消息向前传递，绑定的TTL逐渐递减，当减至0时，便停止搜索。DHC是基于层次树的搜索，搜索深度自然受到层次树级数的约束，而不会导致消息泛滥，因此，DHC对搜索深度没有实施专门控制。4 DHC性能检验本节将通过仿真试验来检验DHC算法的性能，主要考察目标是：随着servent总数的增长，DHC算法的搜索性能的变化情况。4.1 仿真试验设置在试验中，首先生成L个类别，类别特征包括均值向量和方差向量，因为仿真原型是Bloom Filter向量，故设均值向量是高维布尔向量，每一维的数值随机取为0或1，方差向量的每一维也是随机生成，取值范围见表2。每个servent随机分配S个类别，按照类别的均值和方差，以正态分布为每类生成一个样本，这些样本代表servent上的文件。以随机顺序，令servent逐个加入系统，按照算法AD对样本进行层次聚类。待所有servent加入系统并完成聚类后，令每个servent分别发起20次搜索，query的生成方式与样本相同，是属于已有类别的一个向量。从发起servent出发，按照算法E进行搜索，若样本与query的距离小于阈值，则认为匹配。最终，记录试验结果，计算平均值。仿真程序建立在Gnutella v0.4协议之上，并选择Gnutella为参照基准，用一台计算机的不同端口代表不同的servent。表2 参数设定符号描述取值与分布Nservent总数103,5*103,1*104,2*104,9*104,105判定匹配与否的距离阈值6.4Sservent包含的样本数量均匀分布于1,10 L类的数量50D样本向量维数1024Var方差向量的每一维均匀分布于0.05,0.2NbGnutella邻居数量的上限4TTLGnutella消息传播的最远距离74.2 结果与讨论我们从查全率、平均消息数量、平均路径长度和更新消息数量四方面来考察DHC的搜索性能。查全率(Recall)的计算公式如公式(4)所示，平均消息数量是指搜索所导致的消息总数的平均值，平均搜索深度是指搜索路径长度的平均值，更新消息数量是指插入节点所引发的更新其他节点的消息数量。(4)其中，Result是搜索结果集合，Sample是系统所有样本集合。 图4 查全率图5 平均消息数量图6 平均搜索深度 图7 更新消息数量1) DHC与Gnutella的性能比较图4给出了DHC和Gnutella的Recall曲线。当N=103时，Gnutella的搜索消息可以遍布每一个servent，故Recall为100%，随着N的增长，Recall陡然降低，原因是：在TTL的约束下，搜索范围相对缩小。当N=2*104时，Recall已降低至仅为23.0%，之后，曲线下降趋势逐渐趋于平缓。可见，N对Gnutella的Recall有着决定性的影响，较大的servent数量会给Gnutella带来很差的Recall。相对地，DHC的Recall一直稳定在90至80 之间，随N的变化无明显变化。DHC以分级聚类的层次树为搜索结构，避免对大量无关节点进行搜索，将搜索焦点集中在那些成功可能性大的节点上，因而，既提高了Recall，又减少了消息数量。DHC对消息数量的节省可以从图5直观地看出，当N从103增长到105，DHC的消息数量仅从300变化到700，增长趋势呈线性，增幅缓慢；相比而言，Gnutella消息数量在DHC的4倍以上，且增幅明显，是从2.02*103增加到3.88*103；可见，DHC在保证高查全率的基础上，可以有效控制消息数量，节省网络负载。2) DHC搜索深度的变化由于DHC是基于层次树的搜索，搜索深度自然受到层次树级数的约束，因而，DHC对搜索深度没有实施专门控制。由第2节的理论分析知道，随着servent数量的增长，层次树的级数呈对数级增长，故而期望搜索深度亦呈对数级增长，图6的仿真试验很好地验证了这一点。图6的横坐标为servent数量的对数，纵坐标为平均搜索深度，由数据的分布可以看出二者关系近似为线性（图中直线由数据拟合而得），试验很好地验证了：在DHC算法中，搜索深度随servent增长呈对数关系变化。3) 更新消息数量的变化在构建和维护层次树的过程中，需要不断调整相关节点的信息，比如：插入一个新节点需要调整父节点的聚类中心和子节点信息，而由于节点是分布在不同servent上，故更新工作需要多个servent通讯来完成。层次树更新代价的评估便是一个必不可少的环节，它是决定DHC算法实用性的一个关键因素。插入节点和删除节点互为逆过程，更新消息数量规模相同，故我们仅考察插入节点过程中引发的更新消息。在图7的仿真试验中，我们考察对象是一个N=1000的系统，为了更清楚地观察更新消息数量变化趋势，令每个servent只包含一个样本，随着样本逐个加入，层次树的节点数量和级数逐渐增长，引发其他节点更新的机会也越来越多，但是，我们可以清楚地看到更新消息数量与已有节点数量的对数呈线性关系，可以得出结论：更新消息数量限制在O(logN)规模，故而，DHC算法而不会因更新导致消息泛滥。4) 讨论由于层次树级数的理论值为，那么若样本总数M保持稳定，则级数由分支数B决定。如果B过小，会引起节点过多、级数过大，导致搜索时间和信息存储总量的增加。增大分支数B可以起到减少级数的作用，增大分支数B的唯一办法是加大类内距离，调整上下限函数，例如改为。但是，过分B过大也会导致某些问题，B增大，类内距离即增大，类的内聚程度下降，导致查全率下降，比如某些节点虽是潜在结果，但受到其他兄弟节点的影响，导致父节点的聚类中心与query相去甚远，故失去了被搜索的机会，这也正是试验中Recall没有达到100%的原因（图4-1）。另外，增大B还会导致部分servent的存储负担过重，比如，极端情况下，一个根节点包含所有样本，所在servent需要分配巨大的存储空间来储存这些节点信息。在设计真实系统时，分支数范围的界定应该折中考虑多项因素：期望搜索时间、期望查全率、信息存储总量和单一servent最大存储量等。我们的试验取类内距离的上下限函数分别为，不同样本数据的多次试验表明，层次树分支数的变化范围在210之间，满足上述各项因素的一般考虑。5 结论P2P系统网络规模的不断扩大，对集中式搜索算法提出了挑战，表现在信息实时性、服务器负荷能力、网络负载和容错性等方面。分布式搜索算法将搜索任务分解到整个网络的各个参与者中，以适应增长的网络规模。但是，只有满足可扩展性的分布式搜索算法才真正具有应用价值。本文研究对象聚焦在内容索引方式的P2P系统，因为基于向量的内容索引相比于基于Key的DHTs索引可以提供更高质量的搜索结果。但是，已有分布式搜索算法没有解决内容索引的搜索可扩展性问题。本文从聚类的角度，提出了一种新的DHC算法，它可以增量式地构建一棵关于向量样本的聚类层次树，以之为搜索结构，可以保证搜索深度的有限性。在物理层上，层次树的节点分置在各个servent上，并可以根据网络负载状况和系统性能要求进行节点备份。为了保证搜索质量，我们采用了Widyantoro算法，在聚类的过程中，保证聚类节点的类内均匀性和类间单调性，以求克服输入顺序敏感性问题。初步的仿真试验通过查全率、平均消息数量、平均路径长度和更新消息数量四项指标检验了DHC算法的搜索性能，结果表明：相比于Gnutella搜索算法，DHC算法查全率更高、更加稳定，并且节省消息数量，期望搜索深度和期望更新代价限制在O(logN)规模，是一个可扩展的搜索算法。参 考 文 献1 Morpheus. http:/www.morpheus-2 Gnutella. 3 Clarke, Ian, Sandberg, Oskar, Wiley, Brandon, and Hong, Theodore W. Freenet: A Distributed Anonymous Information Storage and Retrieval System. In: Proc. of the ICSI Workshop on Design Issues in Anonymity and Unobservability. Berkeley, CA: International Computer Science Institute, 2000.4 Zhao, B., Kubiatowicz, J., and Joseph, A. Tapestry: An infrastructure for fault-tolerant wide-area location and routing. Technical Report UCB/CSD-01-1141, Computer Science Division, U. C. Berkeley . 20015 Rowstron, A. and Druschel, P. Pastry: Scalable, distributed object location and routing for large-scale peer-to-peer systems. In: Proc. Middleware 2001. 2001.6 Ratnasamy, S., Francis, P., Handley, M., Karp, R., and Shenker, S. A scalable content-addressable network. In: Proc. ACM SIGCOMM'01. 2001.7 Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. Chord: A scalable peer-to-peer lookup service for Internet applications. In: Proc. ACM SIGCOMM'01. SanDiego, CA: 2001.8 Salton, G., Wang, A., and Yang, C. A vector space model for information retrieval. Journal of the American Society for Information Science, 1975, 18: 613-6209 Carmel, D., Amitay, E., Herscovici, M., Maarek, Y., Petruschka, Y., and Soffer, A. Juru at TREC10 - Experiments with Index Pruning. In: Proc. 10th Text REtrieval Conference(TREC). 2001.10 Bloom, B. Space/time Trade-offs in Hash Coding with Allowable Errors. Communications of ACM, 1970, 13(7): 422-42611 Bawa, Mayank, Bayardo Jr., Roberto J., Rajagopalan, Sridhar, and Shekita, Eugene J. Make it Fresh, Make it Quick - Searching a Network of Personal Webservers. In: Proc. 12th International World Wide Web(WWW) Conference. 2003.12 Cuenca-Acuna, Francisco Matias and Nguyen, Thu D. Text-Based Content Search and Retrieval in ad hoc P2P Communities. Technical Report DCS-TR-483. Rutgers University. 200213 Ng, Cheuk Hang and Sia, Ka-Cheug. Peer Clustering and Firework Query Model. In: Proceedings of 11th World Wide Web Conference. 2002.14 Ramanathan, M. K., Kalogeraki, V., and Pruyne, J. Finding good peers in peer-to-peer networks. In: International Parallel and Distributed and Computing Symposium. 2002.15 Pavel, Berkhin. Survey of Clustering Data Mining Techniques. Accrue Sotware. 200216 Widyantoro, D. and Yen, J. An Incremental Approach to Building a Cluster Hierarchy. In: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM02). Maebashi City, Japan: 2002.17 Jain, A. K., Murty, M. N., and Flynn, P. J. Data clustering: a review. ACM Computing Survey, 1999, 31(3)