超级节点网络中的并行查询和排序机制

—97— 超级节点网络中的并行查询和排序机制 谭义红 1,2，林亚平 1，欧阳竟成 1，李 彬 2 (1. 湖南大学计算机与通信学院，长沙 410082； 2. 长沙大学信息与计算科学系，长沙 410003) 摘 要：超级节点网络中的超级节点可能成为网络性能的瓶颈并影响检索结果的统一排序，针对该问提出一种并行查询和排序机制。给 出类特征等索引建立方法和查询节点选择算法，减少超级节点的存储和计算负担，使其在负载能力范围内，尽可能多地连接普通节点。在 获取全局参数的前提下，提出查询节点的查询和排序方法，以提高检索质量。实验结果验证了该机制的有效性。 关键词：超级节点网络；信息检索；并行查询 Parallel Query and Ranking Mechanism in Super-peers Network TAN Yi-hong1,2, LIN Ya-ping1, OUYANG Jing-cheng1, LI Bin2 (1. School of Computer and Communication, Hunan University, Changsha 410082; 2. Department of Information and Computing Science, Changsha University, Changsha 410003) 【Abstract】Super peers in super-peers network may become the network performance bottleneck and affect retrieval result global ranking. Aiming at this problem, this paper presents a parallel query and ranking mechanism. A building method for indexes such as class feature and a selection algorithm for query peers are presented to decrease the storage and computation burden of super peers and make it connect more common peers as possible in the scope of load capacity. A query and ranking method of query peers is presented to improve retrieval quality. Experimental results show that the mechanism is efficient. 【Key words】super-peers network; information retrieval; parallel query 计 算 机 工 程 Computer Engineering 第 36 卷 第 2 期 Vol.36 No.2 2010 年 1 月 January 2010 ·网络与通信· 文章编号：1000—3428(2010)02—0097—03 文献标识码：A 中图分类号：TP396 1 概述 在超级节点网络中，关键技术是网络的组织和查询机制。 查询机制主要包括查询和排序，传统方法通常采用集中式查 询处理方式[1]。由于超级节点连接普通节点的规模不断扩大， 因此超级节点可能因负载过重而成为网络瓶颈。已有很多研 究者对网络瓶颈问题进行研究[2-3]，他们提出的方法虽然在一 定程度上解决了超级节点负载平衡问题，但没减少超级节点 的处理负担。 传统的超级网络排序处理方法大多基于本地信息计算文 档相似度，在没有获取全局参数的情况下，计算出来的相似度 不具可比性，将影响检索结果统一排序，进而影响检索结果 的质量。近年来，人们对此展开了研究[4-5]，但未涉及超级节 点网络的排序问题。因此，本文提出一种并行查询和排序机制。 2 超级节点网络模型 本文的超级节点网络模型类似 EJDPC[2]系统，网络模型 如图 1 所示。 p1 p2 p3 p5p4 p3 p2 SP2 SP4 SP1 SP3 图 1 超级节点网络模型 网络采用 2 层结构管理模式来组织所有节点。网络中节点 分为超级节点(如 SP1, SP2 节点)和普通节点(如 p1, p2 节点)。 一个超级节点与若干个普通节点连接构成局部子网，在局部 子网中，超级节点作为集中服务器，管理相连的普通节点。局 部子网通过超级节点之间互连，而相互连接构成超级节点网 络。普通节点按语义相关性加入到相应的超级节点。 3 并行查询和排序机制 该机制的基本步骤如下：超级节点根据普通节点发送的 相关信息建立索引。当超级节点接收到查询请求时，先获取 全局参数值，计算各个节点的相关度，选择相关度超过某一 阈值的节点，作为查询节点，并将查询请求和全局参数信息 发送到所有查询节点。然后查询节点利用全局参数信息，按 传统查询排序方法，计算文档与查询串的相似度，并将检索 结果发送到查询请求节点。 3.1 查询节点的选择策略 3.1.1 超级节点索引 假设超级节点网络中每个节点 p 都有唯一的标识符，记 作 PID。为了便于查询和排序，超级节点建立节点特征索引、 类特征索引和子网汇总特征索引，分别描述如下： 当普通节点加入超级节点时，将节点特征和类特征信息 基金项目：湖南省教育厅科研基金资助项目(07B007) 作者简介：谭义红(1971－)，男，副教授、博士研究生，主研方向： 数据挖掘，P2P 信息检索；林亚平，教授、博士、博士生导师； 欧阳竟成，博士研究生；李 彬，讲师 收稿日期：2009-07-18 E-mail：yhtan09@163.com —98— 发送到超级节点。节点特征以三元组(PID, N, V(p))示，其 中 ， N 表 示 节 点 共 享 的 文 档 数 ； 1 1 1( ) { , , ,V p t tf dn= < > 2 2 2, , , , , , }m m mt tf dn t tf dn< > < >" ， it 为特征词， itf 为 it 在节点 共享文档中出现的次数， idn 为节点共享文档中包含 it 的文档 数，1≤i≤m，m 为节点共享文档中不相同特征词的个数。类 特征是表示普通节点聚类后，加入到该超级节点的类(C)信 息，用四元组(PID, CID, N, V(C))表示，其中，CID 为类 C 的 标 识 符 ； N 表 示 该 类 的 文 档 数 ； 1 1 1( ) { , , ,V C t tf dn= < > 2 2 2, , , , , , }m m mt tf dn t tf dn< > < >" ， it 为特征词， itf 为 it 在类 C 文档中出现的次数， idn 为类 C 文档中包含 it 的文档数，1≤ i≤m，m 为类 C 文档中不相同特征词的个数。超级节点接收 这些信息建立相关索引。由子网中所有节点特征建立节点特 征索引，由子网中所有类特征建立类特征索引。当普通节点 中有更新时，将相关更新信息发送到超级节点，超级节 点及时更新索引。当节点离开网络时，超级节点自动将与该 节点有关的索引信息全部删除，使超级节点的索引信息总是 保持最新。从节点特征索引和类特征索引中，可以很方便地 获取子网中的全局信息。 为了获取网络中的全局信息，各个超级节点对自身子网 中的节点特征进行统计，得到子网汇总特征，用三元组(PID, N, V(SP))表示，其中，PID 为超级节点标识符；N, V(SP)的 值分别由节点特征中相应值累加得到。超级节点将自身的子 网汇总特征发送给其他超级节点，各个超级节点根据所有超 级节点的子网汇总特征建立子网汇总特征索引。此时，所有 超级节点都能获取整个网络中的全局信息。 3.1.2 查询节点选择 超级节点接收到查询请求后，根据索引计算子网中普通 节点与查询请求的相关度，选择更有可能包含检索结果的节 点作为查询节点。对于查询串 Q={t1,t2,…,tm}，节点 p 与超级 节点关联的类为 C，则用 score(Q,C)表示查询串与节点(类) 的相关度，计算公式如下： , 1 ( , ) m i C i score Q C Weight = = ∑ , ,i C i C iWeight T I= × , , , ( / _ ) i C i C i C C tf T tf qw avg qw = + lg( 0.5) / lg( 1.0) i i n nfI n += + (1) 其中，tfi,C 是查询词 ti 在 C 中的出现度频率；qwC 是 C 中包含 的特征词数目；avg_qw 是网络中全部文档包含的平均特证词 数目；n 是网络中的总文档数；nfi 是网络中包含 ti 的文档数。 对子网中所有节点按式(1)计算相似度，选择相似度超过 设定阈值 θ1 的节点作为查询节点，得到查询节点集，记为 SelectPeerSet={p1,p2,…,pn}，获取查询词出现的文档数和总文 档数，得到全局参数集，记为 GlobalSet={n,,,…, }，并将查询请求 Q 和 GlobalSet 发送到 SelectPeerSet 中各个节点，完成查询节点选择和搜索操作。具体算法如下： 算法 1 查询节点选择算法 输入：Q，索引，θ1 输出：SelectPeerSet, GlobalSet (1)//获取 n,nsp 为超级节点数目 n=0; For j=1:nsp do n=n+ Nj GlobalSett=｛n｝ (2)//对所有查询词 ti 的 tfi,C For i=1:m do //计算查询词 ti 的 tfi,C tfi,C= V(C).tfi //计算查询词 ti 的 nfi For i=1:nsp do nfi= V(SP).dnj GlobalSet= GlobalSet∪｛｝ (3)//计算子网中所有节点(np)相关度 For j=1:np do //按式(1)计算各个节点的相似度 Sj=calS(pj); if (Sj>θ1) //选择超过 θ1 的节点，加入查询节点集 SelectPeerSet = SelectPeerSet {p∪ j} (4)return SelectPeerSet, GlobalSet 3.2 查询排序策略 查询节点接收到查询请求和全局参数后，通过 cosine 距 离法计算查询请求与本节点中文档之间的相似度，计算公式 如下： 1 i 2 2 1 1 ( ) ( ) ( ) ( ( )) ( ( )) n j j i j n n j j i j j w q w d sim q,d w q w d = = = ×∑ = ×∑ ∑ (2) 其中， , ,( ) lgj i j i i j i j nw d tf idf tf nf = × = × ，tfj,i 是特征词 tj 在文档 di 中出现的频率，可从本地索引中获取，n 为所有文档的数 目，nfj 为包含特证词 tj 的文档数，这些数值可从超级节点传 送的全局参数集 GlobalSet 中获取，因此，各个节点计算得 出的 sim(q,di)是具有可比性的，能真实反映文档与查询请求 的相似度，可以参与统一排序。各个查询节点选择超过设定 阈值 θ2 的文档作为检索结果，并返回给查询请求节点。 4 实验 4.1 实验环境 本实验的目的是测试排序和合并后检索结果的质量，以 及超级节点出现负载过重的概率。在实验中，网络拓扑产生 模块采用美国乔治大学的 GT-ITM 软件包，原因是 GT-ITM 作为著名的开源代码的网络拓扑产生系统，可以产生类似于 实际网络中存在的多个局域网、城域网的混杂联网模式。实 验在一台 PC 机上完成，PC 机的配置为 CPU P3.0 GHz，内存 1 GB，操作系统为 Windows XP。实验用的文档集是 SMART 系统中使用的测试文档集 CACM，CACM 包含约 30 000 个计 算机类文档摘要和约 200 个查询，为了更好地反映基于 Internet 的现实应用中信息消费的情形，文档集按 80/20 方式 分布到各个节点，将 30%的文档进行复制，复制份数按 50%, 30%, 20%概率分别复制 1 份、2 份、3 份。为了消除实验误 差，实验结果取 5 次实验的平均值。实验产生 10 000 个节点， 各节点随机加入网络并提交查询。 4.2 实验内容与结果 4.2.1 检索结果测试 实验比较了 EJDPC 和本文算法的查准率和查全率。通过 设置阈值 θ1, θ2，测试算法的查全率和查准率。EJDPC 的检 —99— 索结果只与 θ2 有关，为了便于比较测试结果，将 θ1 的值设 为 0, 0.6, 0.7，分别测试本文算法的查全率和查准率，通过设 置 θ2 的不同值，得到的结果如图 2 和图 3 所示。从图 2 可以 看出，当 θ1 为 0 时，即不考虑查询节点的选择，EJDPC 和 本文算法的查全率较接近，随着 θ1 值的增大，本文算法的查 全率略有降低，主要原因是超级节点在过滤查询节点时，剔 除了一些只包含少量相关文档的节点。图 3 显示本文算法的 查准率明显高于 EJDPC，主要原因是它采用全局参数进行排 序。随着 θ1 值的增大，其查准率逐步提高。 0.0 0.2 0.4 0.6 0.8 1.0 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 θ2 查全 率 EJDPC 本文算法，θ1=0 本文算法，θ1=0.6 本文算法，θ1=0.7 图 2 查全率比较 0.0 0.2 0.4 0.6 0.8 1.0 0.50 0.55 0.60 0.65 0.70 0.75 0.80 0.85 0.90 0.95 1.00 θ2 查准 率 EJDPC 本文算法，θ1=0 本文算法，θ1=0.6 本文算法，θ1=0.7 图 3 查准率比较 4.2.2 超级节点出现负载过重的概率测试 超级节点连接普通节点的规模会影响超级节点的负载平 衡。通过超级节点连接的普通节点数，比较 EJDPC 和本文算 法中超级节点出现负载过重的概率，得到的实验结果如图 4 所示。由图 4 可知，在超级节点连接的普通节点数相同的情 况下，本文算法中超级节点出现负载过重的概率明显低于 EJDPC。一方面是因为普通节点上传的仅是元数据，数量远 低于索引数据，导致超级节点要接收、处理和存储的数据量 大幅减少。另一方面，由于超级节点只负责选择查询节点处 理，将复杂的查询操作分散到各个查询节点，因此进一步减 少了超级节点的处理时间。 100 200 300 400 500 600 0.0 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8 普通节点数 出现 负载 过重 的概 率 EJDPC 本文算法 图 4 超级节点出现负载过重的概率 5 结束语 本文机制有效减少了超级节点的存储和计算负载，提出 的全局参数获取方法使查询和排序可以在各个查询节点上并 行完成，提高了检索结果的质量。 参考文献 [1] Shen Hengtao, Shu Yanfeng, Yu Bei. Efficient Semantic-based Content Search in P2P Network[J]. IEEE Transactions on Knowledge and Data Engineering, 2004, 16(7): 813-826. [2] Airiau S, Sen S, Dasgupta P. Effect of Joining Decisions on Peer Clusters[C]//Proc. of the 5th International Joint Conference on Autonomous Agents and Multiagent System. Hakodate, Japan: [s. n.], 2006. [3] Montresor A. A Robust Protocol for Building Super Peer Overlay Topologies[C]//Proc. of the 4th International Conference on Peer-to-Peer Computing. Zurich, Switzerland: [s. n.], 2004. [4] 何盈捷, 王 栅, 杜小勇. 纯 Peer to Peer 环境下有效的 top-k 查 询[J]. 软件学报, 2005, 16(4): 540-552. [5] Cuenca-Acuna F M, Peery C, Martin R P, et al. PlanetP: Using Gossiping to Build Content Addressable Peer-to-Peer Information Sharing Communities[C]//Proc. of HPDC’03. Seattle, USA: [s. n.], 2003: 236-249. 编辑 陈 晖