《PeertoPeer环境下基于内容的智能搜索.doc》由会员分享，可在线阅读，更多相关《PeertoPeer环境下基于内容的智能搜索.doc（10页珍藏版）》请在三一办公上搜索。
1、Peer-to-Peer环境下基于内容的智能搜索摘要 目前大多数P2P系统只支持基于文件标识的搜索，大大限制了P2P的应用范围纯P2P网络所采用的广播式搜索盲目低效，浪费网络带宽提出了P2P环境下基于内容的智能搜索算法利用向量空间模型进行基于相似度的查询节点对以往的查询进行查询聚类，对当前的查询，根据查询类选择最有可能包含查询结果的节点发送查询，提高了搜索的效率随着查询的进行，查询类可以自动调整，维护代价不大，具有自适应的特点实验证明，基于内容的智能搜索在保证查询效果的前提下大大提高搜索的效率关键词 P2P；相似度；聚类；智能搜索中图法分类号 TP311Intelligent Search b
2、ased on content of documents in peer-to-peer networkAbstract Most existing Peer-to-Peer (P2P) systems only support simple title-based search, which is limited in functionality. Broadcast search is widely used in pure P2P network, which is not efficient and costs a lot of bandwidth. An intelligent se
3、arch algorithm based on content of document is proposed. Vector space model (VSM) is used to do similarity search. Each peer does query clustering with the past queries. For a new arriving query, the most possible peers that have the query answers are selected according to the query cluster to send
4、the query, which improves the search efficiency. With queries done, query clusters can be adjusted automatically with a little cost. It is proved by experiments that the intelligent search algorithm can greatly improve the search efficiency, and meanwhile guarantee the query effectiveness.Key Words
5、P2P; similarity; clustering; intelligent search1 引言目前大多数P2P系统只支持基于文件标识的搜索，例如：Napster1和Gnutella2使用文件名进行搜索，DHT使用基于key（由Hash函数产生）的查找，代表系统为Chord3这些系统都不支持基于内容的搜索，大大限制了P2P的应用范围本文主要考虑如何在纯的P2P环境下进行基于内容的搜索假设网络中的每个节点都维护一个文档集给定一个查询，可能是几个关键字，一个短语，一个句子，或者一个段落，搜索网络中与查询语义相近的文档我们利用向量空间模型VSM4（Vector Space Model）计算文档
6、和查询的相似度，搜索网络中的节点，返回与查询相似的文档纯的P2P网络（如Gnutella）中的搜索是一种广播式的搜索，查询被广播发送给所有的邻居节点，不管它们是否真正含有查询结果广播式的搜索具有很大的盲目性，搜索效率低下，而且造成了网络带宽的极大浪费我们提出了一种基于内容的智能搜索算法，节点根据以往查询提供的信息，进行Peer（节点）选择，将查询发送给那些最有可能包含查询结果的邻居节点，提高搜索的效率我们采用的方法是根据查询的内容对查询进行聚类对当前的查询q，计算查询类与查询q之间的相似度，选择与q最为相似的查询类，根据查询类的文档结果分布（不同邻居节点返回的结果数），选择返回结果最多的k个邻
7、居节点发送查询随着查询的进行，查询类可以自动调整，维护代价不大，具有自适应的特点实验证明，基于内容的智能搜索在保证查询效果的前提下大大提高了搜索的效率2 相关工作比较广播式的搜索是一种盲目的搜索，搜索效率低下为了提高搜索的效率，研究者们提出了很多解决方法文5提出了几种在P2P网络中提高搜索效率的策略逐步加深搜索（Iterative Deepening）在一定程度上提高了搜索的效率，但没有解决消息广播发送的问题定向宽度优先的搜索DBFS（Directed Breadth First Search）采用启发式的搜索避免了查询的广播发送，但没考虑查询的语义本地索引（Local Index）有助于提高
8、搜索的效率，但索引维护的代价很大Freenet6只支持key（由Hash函数产生）的查找，不支持基于内容的查找，大大限制了它的使用范围路由索引（Routing Index）7与广播式的搜索相比，提供了目标节点的方向，循序渐进地达到之，不再是盲目的搜索，提高了搜索效率，但索引维护的代价很高，不适于经常动态改变的P2P网络自适应的概率搜索APS（Adaptive Probabilistic Search）8具有自学习的特点，但它需要为每个对象建立索引，需要很大的存储空间，而且它只支持对单个对象的查找，不支持对多个对象的查找基于内容的智能搜索根据查询聚类，选择最有可能包含查询结果的节点发送查询，避免
9、了消息的泛滥根据查询的内容进行聚类，考虑了查询的语义随着查询的进行，查询类可以动态更新，维护代价很小，具有自适应的特点3 纯P2P网络中基于内容的搜索纯P2P网络（如Gnutella）中不存在中心服务器，各个节点的地位一样，可以动态地加入和退出网络，节点上数据的放置由用户自己决定，网络拓扑结构是任意的假设网络中的每个节点都维护一个文档集，给定一个查询（用一组关键字进行表示），搜索网络中与查询相似的文档我们利用向量空间模型VSM（Vector Space Model）进行本地的文档检索VSM是信息检索中的广泛使用的检索模型，它用向量表示查询和文档：（w1, w2, w3, wn），其中wi为第i
10、个特征项的权重一般选用词作为特征项，词的权重一般采用TF*IDF规则产生，TF（term frequency）表示词频，IDF（inverse document frequency）表示逆文档频率TF*IDF规则综合考虑了文档中词的频率和文档集中包含该词的文档数，保证词频高并且含该词文档数少的词的权重越高文档中词的权重通过如下TF*IDF公式计算： (1)其中，wi,j为词 ti 在文档dj中的权重，fi,j为词ti在文档dj中的词频，N为文档的总数，ni为文档集中出现ti的文档数，分母为归一化因子查询向量的计算相对简单，查询中关键字的权重要么是1要么是0，如果该关键字在查询中出现，则权重为1
11、，否则为0同样，我们也对查询向量进行归一化处理文档和查询的相似度通过计算文档向量和查询向量的夹角余弦进行衡量，具体公式为：(2)其中，,分别为文档dj和查询q的向量表示，wi,j和wi,q分别对应词ti在文档dj和查询q中的权重向量之间的夹角余弦通过计算向量的点积得到由于文档dj和查询q的向量都经过归一化处理，因此相似度函数又可以写成：纯P2P网络中采用的是广播式搜索每个节点除了搜索它的本地索引，还将查询广播发送给它的所有邻居节点进行搜索搜索的范围由查询的跳数TTL（Time-to-live）给出，查询每转发一次，TTL减1，当TTL等于0时，就停止传播查询节点找到结果就把结果原路返回给查询的
12、发起节点为防止回路的产生，每个查询消息都有唯一编号如果该查询先前已经收到，说明发生了回路，则不必再传播它Gnutella采用的查询是基于文件名的，我们将查询进行扩展，包含一组关键字每个节点维护一个倒排索引，检索与查询相关的文档，并根据VSM计算文档与查询的相似度规定一个相似度的门槛值T，凡是与查询的相似度大于等于T的文档均作为查询结果返回搜索TTL范围内的所有节点，得到与查询相似的所有文档4 基于内容的智能搜索算法广播式的搜索盲目低效，浪费网络带宽我们希望在搜索的过程中，节点可以根据以往查询提供的信息，将查询发送给那些最有可能包含查询结果的邻居节点，从而提高搜索的效率我们采用的方法是对查询进行
13、聚类，然后根据查询类对当前的查询进行Peer选择最后，根据Peer返回的结果对查询类进行调整4.1 查询聚类每个节点保存以往的查询结果，并对查询进行聚类我们根据查询的内容对查询进行聚类查询之间的相似度通过计算查询向量之间的夹角余弦得到，如式(2)查询聚类的算法我们采用K-Means算法9具体步骤如下：STEP 1：任意选择kC个查询，作为类中心的估计；STEP 2：对每一个查询q，计算q与kC个类中心的距离（相似度，通过计算向量之间的夹角余弦得到），将q归入到距离q最近的类别中；STEP 3：重新计算各类的中心，计算方法为所有查询向量的算术平均；STEP 4：跳转到STEP 2，直到各类中心稳
14、定K-Means算法通过不断的迭代，最终将查询划分为kC类，每类聚集在类中心周围的一个小区域，而且类与类间是可以比较明显地区分K-Means算法的时间复杂度为，其中，nq表示总的查询数，kC表示查询类的个数，l表示算法收敛所需的迭代次数一般情况下，kC和l都事先固定，算法的时间复杂度变为一个线性的复杂度K-Means算法的空间复杂度为，只需要kC个查询类和nq个查询的存储空间我们可以限制nq的最大数目，并利用LRU（Least recently used，最近最少使用）策略进行淘汰，保证节点存储常用的查询4.2 利用查询类进行Peer选择对同一类查询，我们计算查询的中心向量，用以表示查询类，计
15、算方法为所有查询向量的算术平均例如：q1, q2, q3为一类查询，用C1表示该查询类，则C1的向量表示为为了进行Peer选择，节点还需记录查询的结果分布，即不同邻居节点返回的结果数我们对同类查询的文档结果分布也进行平均，用来表示查询类的文档结果分布设查询q的文档结果分布为(Nq,1, Nq,2, , Nq,n)，其中Nq,i为邻居节点Pi返回的结果数，n为节点P的邻居节点数用|C|表示查询类中查询的个数，查询类C的文档结果分布为：, (3)对当前的查询q，计算每个查询类与查询q的相似度，通过计算向量之间的夹角余弦得到，如式(2)选择与q最为接近的查询类C，根据C的文档结果分布，将查询发送给返
16、回结果最多的k（kn）个节点假如不存在与q相似的查询类，我们将查询广播发送给所有的邻居节点例如：节点A进行查询聚类，得到查询类C1、C2、C3，C1、C2、C3的文档结果分布分别为(5, 10, 0)、(20, 0, 10)和(0, 5, 10)，表示从邻居节点B、C、D返回的结果数对查询q1，我们利用式(2）计算查询q1与查询类C1、C2、C3的相似度，选择与q1最相似的查询类C1，根据C1的文档结果分布，将查询q1发送给节点B、C（假设k=2）；对查询q2，不存在与q2相似的查询类，将查询q2广播发送给节点B、C、D根据查询类进行Peer选择可能导致消息死锁的形成，例如：节点A将查询发送给
17、邻居节点B、C、D，它们都不包含查询结果节点B认为节点A、C、D是最好的邻居节点（最有可能包含查询结果），节点C认为节点A、B、D是最好的邻居节点，节点D认为节点A、B、C是最好的邻居节点这样，消息形成死锁，查询不能发送到网络中其他的节点上为了解决这个问题，我们额外随机选择一小部分邻居节点发送查询，降低死锁发生的概率下面，我们给出基于内容的智能搜索算法IntelligentSearch假设已经通过K-Means算法对查询进行聚类，生成kC个查询类IntelligentSearch根据已有的查询类，进行Peer选择，具体步骤如下：STEP 1：计算查询q与每个查询类的相似度假如存在与查询q相似的
18、查询类，选择与查询q最相似的查询类C；否则，将查询q广播发送给节点P的所有邻居节点；STEP 2：根据查询类C的文档结果分布，选择k个返回结果最多的节点发送查询为了避免消息死锁的形成，额外随机选择几个节点发送查询；STEP 3：根据邻居节点返回的查询结果，记录查询q的文档结果分布，保存查询q；STEP 4：将查询q归入查询类C，每隔一段时间利用K-Means算法重新调整查询类IntelligentSearch根据以往的查询提供的信息，选择最有可能包含查询结果的节点发送查询，避免了查询的广播发送，提高了搜索的效率4.3 查询类的维护对以往的查询进行查询聚类，随着查询的进行，查询类可以自动调整，维
19、护代价不大IntelligentSearch的第4步，我们将查询q归入与q最相似的查询类C，重新计算查询类的中心向量，得到新的查询类C的向量表示同时，根据查询q的文档结果分布，重新计算查询类C的文档结果分布每隔一段时间，调用K-Means算法，调整查询类基于内容的智能搜索通过对查询进行聚类，进行Peer选择，提高了搜索的效率同时，查询聚类只需的时间（kC和l取常数），节点只需存储的查询以及查询类，付出的额外代价很小随着查询的进行，查询类可以自动进行更新，维护代价也不大实验证明，基于内容的智能搜索算法是有效的5 实验我们通过实验验证基于内容的智能搜索算法的有效性，对算法的查询效果和搜索效率进行实
20、验分析查询效果主要从用户的角度考虑，反映系统的服务质量Qos（Quality of Service）；搜索效率主要从系统的角度进行考虑，力图用最少的资源，获得最多的输出5.1 实验设置表4.1 实验参数表4.1 实验参数所有实验都在一台PC机上完成，PC机的配置为CPU P4 1.6GHz，内存1GB，操作系统Windows XP模拟程序由JAVA编写，网络拓扑结构基于Power-law，由PLOD算法10产生研究显示Gnutella的网络拓扑结构接近Power-law11，Internet也符合Power-law规律，因此我们的模拟尽量接近现实中的P2P网络以下是实验涉及的一些参数：参数名称
21、缺省值描述Network TopologyPower-law网络拓扑结构，每个节点的平均出度为7Network Size1000网络中的节点数TTL5Time-to-live，查询消息的跳数K3选择K个节点发送查询ClusterNum10聚类的个数NewQueryNum10每个节点上新来10个查询就重做一次K-Means，调整查询聚类注意：PLOD算法产生的网络是一个无向图，每个节点平均出度为7，相当于无向图中有3500条无向边实验中，我们根据查询类选取K个返回结果最多的节点发送查询，并没有象4.2节那样，额外随机选择几个节点发送查询以避免消息死锁的形成测试文档集我们采用SMART系统12中所
22、使用的测试文档集Cranfield，Cranfield包含1398个空气动力学类文档摘要和225个查询文档集的分布采用80-20分布，即将80的文档分布在20%的节点上，余下的20%的文档分布在80%的节点上，文档不允许重复存放在多个节点上80-20分布符合现实P2P系统的情况，网络中只有少部分节点共享自己的文件，大部分节点只是搜索并下载文件5.2 查询效果判断基于内容的智能搜索算法(IntelligentSearch)的查询效果，我们采用信息检索中的查全率（Recall）进行衡量，Recall的计算公式如下： (4)其中，|Ra|为查询结果中与查询相关的文档个数，|R|为文档集中与查询相关的
23、文档数我们将广播式搜索的查询效果作为测试的基准，计算相对Recall作为查询效果的衡量标准，计算公式如下：相对Recall=Recall/广播式搜索的Recall (5)5.2.1 实验1 IntelligentSearch的查询效果我们将Cranfiled的225个查询分为两部分，前100个查询用来建立查询聚类，后125个查询用来测试查询聚类对查询效果的影响从网络中任选10个初始节点，先后执行这两部分查询，计算相对平均Recall,比较IntelligentSearch和RandomSelected（从所有邻居节点中随机选取K个节点发送查询）的查询效果，如图1所示可以看出，RandomSel
24、ected的相对平均Recall稳定地维持在一个较低的水平，而IntelligentSearch的查询效果大大好于RandomSelected的查询效果，说明查询聚类的方法是有效的通过查询聚类，我们选取了“较好”的K个邻居，因此比随机选取K个邻居的效果更好IntelligentSearch在访问较少节点（K=3，只有网络平均出度的一半不到）的情况下，依然能得到较好的结果（平均Recall是广播式搜索的56.9%，IntelligentSearch的查询效果不如广播式搜索，是由于它只选择K个最有可能返回结果的节点发送查询，搜索的节点没有广播式搜索多），因此是有效的我们将在5.3节对搜索效率进一步
25、用实验说明图1 IntelligentSearch和RandomSelected的相对平均Recall图2给出了IntelligentSearch和RandomSelected在查询过程中的相对平均Recall，我们以10个查询作为一个观测点，计算10个查询的相对平均RecallQueryNo表示查询的编号，QueryNo对应的值表示QueryNo前后10个查询的相对平均Recall 可以看出，随着查询的进行，IntelligentSearch的查询效果越来越好，这是由于随着查询数目的增加，节点上的查询聚类越来越准确，能为以后的查询提供更好的参考曲线在QueryNo=155时有抖动，是因为我们
26、根据以往的查询结果对当前的查询提供参考，随着查询的进行，聚类需要重新调整RandomSelected由于没有根据查询类进行选择，因此与查询无关图2 查询过程中的相对平均Recall5.2.2 实验2 不同TTL情况下的查询效果IntelligentSearch的搜索范围受到TTL的限制，不能访问TTL之外的节点增大TTL，可以提高IntelligentSearch的查询效果，实验结果如图3所示图3 IntelligentSearch在不同TTL情况下的相对平均Recall (K=3)5.2.3 实验3 增大K对查询效果的影响IntelligentSearch的搜索范围不仅受到TTL的影响，还受
27、到选择节点个数（K）的影响增大K可以提高查询的效果，但也会影响查询的效率，访问更多的节点增大K对搜索效率的影响我们将在5.3节中用实验说明图4给出了IntelligentSearch和RandomSelected在TTL固定K增大的情况下的查询效果可以看出，随着K的增大，IntelligentSearch和RandomSelected的查询效果越来越接近，当K接近网络的平均出度时，这两种算法的查询效果接近广播式搜索因此，需要选择一个合适的K，在兼顾搜索的效率的同时，提高查询的效果图4 增大K对查询效果的影响(TTL=5)5.3搜索效率我们取查询访问的节点数VisitedNodeNum和传递的查
28、询消息数MsgNum作为衡量搜索效率的指标访问的节点数越少，需要传递的查询消息数就越少，搜索的效率就越高，需要付出的代价就越小一般来说，VisitedNodeNum小于MsgNum，因为网络中可能存在回路5.3.1 实验4 IntelligentSearch的搜索效率测试IntelligentSearch的搜索效率同样，从网络中任选10个初始节点发送查询，先执行前100个查询建立查询聚类，再执行后125个查询测试查询聚类的效果，计算平均访问的节点数和发送的消息数，比较三种算法的搜索效率，如图5所示(a) 平均访问的节点数(b) 平均发送的消息数图5三种搜索算法的搜索效率率可以看出，Intell
29、igentSearch和RandomSelected平均访问的节点数还不到Broadcast的一半，需要发送的消息数更少，大约是Broadcast的四分之一 IntelligentSearch平均访问的节点数和发送的消息数略多于RandomSelected，但IntelligentSearch的查询效果远远好于RandomSelected，见实验1因此IntelligentSearch是有效的，它提高了搜索效率，同时兼顾了查询效果比较图5(a)和图5(b)，可以发现，Broadcast发送的消息数（1296）远远大于访问的节点数（719），说明查询过程中发生了大量的回路IntelligentS
30、earch发送的消息数（330）略大于访问的节点数（244），有效地避免了回路5.3.2 实验5 增大K对搜索效率的影响由实验3，我们知道增大K可以提高查询的效果，但同时也降低了搜索的效率，实验结果如图6所示(b) 平均发送的消息数(a) 平均访问的节点数图6 增大K对搜索效率的影响(TTL=5)可以看出，增大K，IntelligentSearch和RandomSelected平均访问的节点数和消息数都随之增加，越来越接近Broadcast因此我们需要选择一个合适的K，在提高搜索效率的同时，兼顾查询的结果5 结论和未来工作本文讨论了P2P环境下基于内容的搜索，提出了一种有效的基于内容的智能搜索
31、算法对以往的查询进行聚类，根据查询类选择最有可能包含查询结果的节点发送查询，提高了搜索的效率查询类可以随着查询的进行自动更新，维护代价小，具有自适应的特点本文只考虑了基于相似度的查询，利用VSM模型检索所有与查询相关的文档，并未对查询结果进行排序，查询结果中往往包含大量与查询无关的文档，同时也消耗了大量的网络带宽我们希望对查询结果进行排序，仅返回给用户相似度最高的文档，提高用户的满意度目前我们正在研究P2P环境下文档集上的top-k查询，已经取得了部分研究成果，下一步将把top-k查询扩展到数据管理的层次，进而扩大P2P搜索的范围参 考 文 献1 Napster Home Page. 2 Gn
32、utella Home Page. 3 I Stoica, R Morris et al. Chord: A scalable peer-to-peer lookup service for internet applications. ACM SIGCOMM Computer Communication Review, 2001, 31(4): 1491604 R Baeza-Yates, B Ribeiro-Neto. Modern information retrieval. Boston, MA: Addison Wesley, 1999. 27305 B Yang, H Garcia
33、-Molina. Efficient search in peer-to-peer networks. In: Proc of the 22nd International Conference on Distributed Computing Systems. Vienna: IEEE Computer Society, 2002. 5146 I Clarke, O Sandberg et al. Freenet: A distributed anonymous information storage and retrieval system. In: H Federrath ed. Pro
34、c of the Workshop on Design Issues in Anonymity and Unobservability. Berkeley: Springer-Verlag, 2000. 46667 A Crespo, H Garcia-Molina. Routing indices for Peer-to-Peer systems. In: Proc of the 22nd International Conference on Distributed Computing Systems. Vienna: IEEE Computer Society, 2002. 23348
35、D Tsoumakos, N Roussopoulos. Adaptive probabilistic search (APS) for Peer-to-Peer networks. Technical report CS-TR-4451, University of Maryland, 20039 A Jain, M Murty. Data clustering: a review. ACM Computing Surveys, 1999, 31(3): 26432310 C Palmer, J Steffan. Generating network topologies that obey
36、 power law. In: Proc of GLOBECOM. San Francisco, CA: IEEE, 2000. 43443811 M Ripeanu. Peer-to-Peer architecture case study: Gnutella network. Technical Report, TR-2001-26, University of Chicago, 200112 C Buckley. Implementation of the SMART information retrieval system. Technical report, TR35-686, Cornell University, 1985
