（计算机系统结构专业论文）p2p网络中topk查询算法的设计与实现.pdf

大连理t 大学硕十学位论文 摘要 近年来，随着信息技术的迅猛发展，信息资源极大丰富，如何在动态的p 2 p 网络环 境中对海量数据进行查找引起了很大的关注。t o p - k 查询就是从数量巨大的信息中选择 最符合查询条件的k 个结果呈现给用户，t o p k 查询作为一种新的查询技术引起了学术 界广泛的关注，主要包括聚合式t o p - k 查询和非聚合式t o p - k 查询两种。然而现有的聚合 式t o p k 查询算法只按照分值标准选择合适的对象返回给查询节点，相同的阈值标准没 有考虑到节点数据分布情况，非聚合式t o p k 查询算法只能排除非法节点，不能排除有 效节点中的非法对象。 针对聚合式t o p - k 查询的缺陷，本论文提出了一种基于p 2 p 网络的混合非一致阈值 聚合t o p - k 搜索算法h n u t a ( h y b r i d n o n u n i f o r i bt h r e s h o l da l g o r i t h m ) ，h n u t a 结合位 置选择标准和分值选择标准，通过对每个节点重新定义阈值，并且对每个对象估计极大 值和极小值，通过比较当前t o p k 和候选集中对象的极大值，除去候选集中的非法对象， 达到减少非法对象传输的效果。针对非聚合式t o p k 查询，提出了一种依托于超级立方 体骨干p 2 p 网络的控制答复数量t o p - k 算法c r n t o p k ( c o n t r o lr e p l yn u m b e rt o p k ) ，该 算法利用向量空间模型在本地查询t o p - k ，然后在父节点上合并结果，通过控制查询答 复数量的方式来减少带宽消耗。最终通过实验评估和性能分析表明本论文提出的算法在 网络带宽消耗和查询响应时间方面要优于其他同类方法。 关键词：p 2 p 网络；直方图；聚合t o p - k 查询；非聚合t o p k 查询 p 2 p 网络中t o p - k 查询算法的设计与实现 d e s i g na n di m p l e m e n to ft o p kq u e r yi np 2 pn e t w o r k a b s t r a c t i nr e c e n ty e a r s w i n lt h er a p i dd e v e l o p m e n to ft h ei n f o r m a t i o nt e c h n o l o g y , i n f o r m a t i o n r e s o u r c e sh a v e b e e ng r e a t l ye n r i c h e d h o wt or e t r i e v et h es m a l la m o u n to ft h em o s tv a l u a b l e i n f o r m a t i o nf r o mt h em a s s i v ed a t ai np 2 pn e t w o r kq u i c k l yh a sb e c o m eag r e a tc h a l l e n g ef o r t h ed a t a b a s ef i e l d t o p - kq u e r i e sb a s e do nr a n k i n ge l e m e n t ss t o pq u e r y p r o c e s s i n gw h e nt h e t o p kr a n k e dr e s u l t sc a l lb es a f e l yd e t e r m i n e di n c l u d i n ga g g r e g a t et o p - kq u e r ya n d n o n a g g r e g a t et o p - kq u e r y g i v e na l la g g r e g a t eo p e r a t i o n , at o p - kq u e r yi st of i n dt h ek o b j e c t sw i t ht h eh i g h e s t ( o rt h el o w e s 0a g g r e g a t ev a l u e s e x i s t i n gt o p - ka g g r e g a t eq u e r y a l g o r i t h mh a st h eu n i f o r mt h r e s h o l da n ds e l e c t st h eo b j e c ta c c o r d i n gt ot h ev a l u es t a n d a r d n e g l e c t i n gt h ed a t ad i s t r i b u t i o n t h ee x i s t i n gn o n - a g g r e g a t i o nt o p - ka l g o r i t h mo n l ys u p p o r t s p e e rp r u n i n gs e a r c l l 。，a n du s e r sc a l ln o ts e a r c ht h ed a t ab a s e do np r u n i n gt h ei l l e g a lo b j e c t t h i sp a p e rp r o p o s e sh y b n dn o n - u n i f o r mt h r e s h o l da l g o r i t h mi np 2 pn e t w o r k , i tr e f i n e s t h et h r e s h o l da c c o r d i n gt ot h ev a l u ea n dp o s i t i o ns t a n d a r d h n u t ac a ne s t i m a t et h eb e s ta n d w o r s t v a l u eo ft h eo b j e c t c o m p a r e db e t w e e nt h et o p ka n dt h eb e s tv a l u ei nt h ec a n d i d a t es e t ， i tc a l lr e m o v et h ei l l e g a lo b j e c tf r o mt h ec a n d i d a t es e t t h i sp a p e rp r o p o s e st o p - kq u e r yi n p 2 pn e t w o r k i td y n a m i c a l l ya d j u s t so ft h eu p p e rs c o r ea c c o r d i n gt ot h el o s sf u n c t i o n t h i s m e t h o dr e d u c e st h er e p l yt r a f f i cb yc o n t r o l l i n gt h en u m b e ro fq u e r yr e p l i e s i na d d i t i o n ， 廿l r o u g he x p e r i m e n t a ls i m u l a t i o na n dt h e o r e t i c a la n a l y s i s ，t h ep r o p o s e da l g o r i t h mi ss u p e r i o r t ot h ec u r r e n tt o p - ka l g o r i t h m i tc o n s u m e sl e s sb a n d w i d t ha n dh a sb e t t e re f f i c i e n c y k e yw o r d s ：p 2 pn e t w o r k ；h i s t o g r a m ；a g g r e g a t et o p k ：n o n - a g g r e g a t et o p - k 大连理工大学学位论文独创性声明 作者郑重声明：所呈交的学位论文，是本人在导师的指导下进行研究 工作所取得的成果。尽我所知，除文中已经注明引用内容和致谢的地方外， 本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请 学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献 均已在论文中做了明确的说明并表示了谢意。 若有不实之处，本人愿意承担相关法律责任。 学位论文题目：竺陛因丝王马唑壅翅笪堕鱼! 垒笪鱼塞塑 作者签名： 盈塞够日期：4 年生月盐日 大连理工大学硕士学位论文 大连理工大学学位论文版权使用授权书 本人完全了解学校有关学位论文知识产权的规定，在校攻读学位期间 论文工作的知识产权属于大连理工大学，允许论文被查阅和借阅。学校有 权保留论文并向国家有关部门或机构送交论文的复印件和电子版，可以将 本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印、或扫描等复制手段保存和汇编本学位论文。 学位论文题目： 垒丝里固缝生垃垦壅固笪区鱼1 出鱼塞盈z z 作者签名： 盈叁筠日期：型耻年丝月丑日 导师签名：3 皇l 日期：塑乒年堡月堑日 大连理工大学硕士学位论文 1绪论 1 1背景 由于p 2 p 网络没有中心服务器，不会因为访问中心服务器造成网络拥塞，这种无可 替代的优势引起了很大的研究热潮。随着计算机硬件和软件性能的提高，发出的请求在 所有节点上都可以进行计算和处理，这也是p 2 p 网络最大的优点。p 2 p 的应用广泛，在 用户间协作，资源共享和网格计算等发面都发挥了很重要的作用。p 2 p 网络同时还可以 增强整个计算机系统的可靠性和容错能力。目前大部分p 2 p 研究都假定所有节点带宽和 处理能力是一样的，但p 2 p 网络中存在着处理能力和性能都不同的节点，具有较强计算 能力和较大带宽的节点被称为超级节点。考虑到这种差异性，在动态网络中把所有的节 点都看成一样是很不合理的。 面对日益丰富的信息资源，用户在获取信息上面希望能够从海量数据中迅速找到少 量最具有价值的信息，而不用让用户从头至尾的逐一挑选【l 】。这种用户需求推动了业务 系统在信息处理方式上的转变。许多数据密集型应用己不再追求搜索结果的完整性，而 只关注如何从海量的数据中快速查询用户最为关心的少量信息。t o p k 查询是根据用户 指定的聚集函数( 单调) 从数据集中检索出函数值最高的前k 个结果。例如当前点击量 在前1 0 名的网站。在许多数据密集型应用中，普遍存在的用户需求是快速搜索用户最 为关心的少量结果。这个问题在信息检索领域得到了很好的应用与研究。例如，在使用 搜索引擎时，用户都能在返回的页面中找到想要的结果。针对该问题，上世纪9 0 年代 末，f a g i n 等人借鉴信息检索相关技术的思想，提出了t o p k 查询的概念。t o p - k 查询的 核心思想是用户只关心数据中极少量的数据，查询引擎只需要找出这些少量数据即可， 由此优化查询处理算法，减少带宽消耗并提高查询处理效率。 1 2 问题的提出和研究内容 t o p k 查询也是当今搜索的热点问题，t o p - k 查询就是查找最满足查询的k 个结果。 t o p k 不关心满足查询条件的所有结果，只是关心满足条件的前k 个结果，极大的减少 了查找的时间，只要满足条件的t o p k 结果出现后，即可停止查询。由于p 2 p 网路的动 态性和可扩展性，为p 2 p 网络中的t o p - k 查询带来了一些挑战。如何在提高准确率的同 时，尽量减少带宽消耗和减少访问节点的个数，已经成为一个重要的思考问题。 基于聚集排序的t o p - k 查询： 目前t o p - k 搜索查询的主流技术是以t a 算法为代表的基于聚集排序的t o p - k 查询。 其核心思想是对每一个对象按照属性评价的降序进行排序，然后采用随机访问和顺序访 p 2 p 网络中t o p - k 奇询算法的设计与实现 问这两种方式在各个节点数据序列上获取数据，计算已访问对象的聚集函数值，并利用 顺序访问的边界阈值来判断t o p - k 查询是否可以结束，其中顺序访问是指对己排序序列 自顶向下的依次访问，随机访问是指从其他节点序列中获取某个对象的值。 p 2 p 网络中基于文件内容的t o p - k 搜索： 首先根据先验概率在父亲节点上利用直方图计算其子节点查询的可能上限，按照节 点可能上限从大到小排序，依次在节点本地利用向量空间模型进行本地的t o p k 查询， 更新父节点的t o p k 结果，同时排除非法节点。 基于文件内容的t o p k 检索其优点是利用直方图结构可以剪裁非法节点，其主要缺 点由于存在损失函数致使可能上限估计不准，排除一些有效节点，同时每个节点都上传 t o p k 结果给其父节点，造成带宽消耗。 总之，目前为止要解决的主要问题： ( 1 ) 检索数据时的带宽消耗 ( 2 ) t o p k 检索数据的准确率 ( 3 ) t o p k 检索时间 本文主要是对p 2 p 网络的拓扑结构进行分析，针对p 2 p 网络的t o p k 算法进行了改 进，对超立方体拓扑结构模型进入了深入的分析，并且依据超级立方体的拓扑结构实现 更高效的t o p - k 算法。 1 3 论文章节组织结构 第一章，即本章，介绍了p 2 p 网络的发展现状和问题；第二章回顾了p 2 p 的发展历 程，阐述了p 2 p 的概念，分析了p 2 p 系统的特点，对p 2 p 网络的拓扑结构作了初步的 介绍，指出了p 2 p 网络的前景应用；第三章介绍了t o p - k 查询的概念以及现存的比较经 典的t o p k 算法；第四章针对目前算法出现的问题引入了新的t o p - k 查询算法，首先提出 了h n u t a 算法，通过位置标准和分值标准结合确定不同节点阈值，达到节省带宽的目 的。其次提出了基于超立方体结构的c r n t o p k 搜索算法，该算法利用展开树将t o p k 查询消息广播到所有的节点，每个节点合并自己与子孙节点的查询结果以形成最优的k 个资源，在父节点合并结果，根节点获得t o p - k 结果集。通过动态调整估计上限来减少 有效节点的误删除，并限制返回结果的个数来减少带宽消耗；第五章主要针对前一章所 提出的两个算法进行了模拟实验，分析了算法的性能，并对改进前后算法的模拟结果进 行了对比分析；最后提出了今后需进一步研究的方向。 大连理工大学硕士学位论文 2 p 2 p 网络的t o p k 查询 2 1p 2 p 概述 计算机技术、通信技术以及建立在计算机和通信技术基础上的计算机网络技术在二 十世纪得到了迅猛的发展。其最主要的特征：计算机网络化，协同计算能力发展以及全 球互连网络( i n t e m e t ) 的盛行。目前，计算机已经走进各行各业，为各行各业的人们提 供服务。另外，虚拟网络f d d i 及a t m 技术的应用，促进了网络的更为迅速的发展， 方便人民的生活。自从二十世纪，i n t e r n e t 开始走迸了千家万户，网络的带宽大幅度增 加，网络的终端系统的处理能力也得到了迅速的增强。由此c s ( c l i e n t s e r v e r ) 模式局 限性也表现的更加明显。例如，访问过于集中而发生中心服务器瘫痪等问题。c s 模式 也没有考虑到终端的计算能力，造成终端资源的浪费。这些因素造成了p 2 p 网络模式渐 渐成为了研究的热点。p 2 p 网络便利网络节点沟通，更加方便的实现共享和交互。p 2 p 网络可以使终端直接连接到别的用户的计算机上面，利用别人计算资源和数据资源，不 必像以前一样必须连接到某台服务器上面，这大大增加了网路的资源和资源利用率。p 2 p 网络模式能够充分利用网络的资源，直接查找利用其他节点的运算能力和资源，其特性 受到了用户的欢迎，有着极其巨大的应用前景。 图2 1p 2 p 网络模型结构图 f i g 2 1 t h es t r u c t u r eo fp 2 pn e t w o r k p 2 p 网络是一个分布式的网络，网络的每一个节点都共享网络中的资源，包括硬件、 p 2 p 网络中t o p - k 奇询算法的设计与实现 软件以及处理能力等，而这些节点无需经过中心的服务器，在这里面的节点既是提供资 源和服务的提供者，同时也是要获取资源和服务的获取者。p 2 p 打破了以往c s 模式中 的要有中心网络服务器的模式，使得每个在网络中的节点都是平等的。 p 2 p 的定义：p 2 p e 2 1 是p e e rt op e e r 的缩写，它是一种对等网络，由大量动态节点组 成。每个网络中的节点( p e e r ) 都是对等的。它们可以任意的加入或者离开网络，可以 协同完成任务。p 2 p 使得网络的沟通变得很容易，可以直接的共享和交互，避免了中心 服务器。与c s 模式相比，不需要像从前一样必须从服务器上去浏览和下载，网络中的 任何设备都能为其他设备提供服务和请求其他设备为之服务，因而数据共享程度更高。 目前基于p 2 p 的w e b 搜索研究的搜索对象是各类w e b 文档，通常以关键词查询的方式 提供服务，因此本质上属于基于关键词的全文搜索。在p 2 p 全文搜索方面，已有很多研 究成果【3 刁】，它们为基于p 2 p 的w e b 搜索提供了一定的技术基础。p 2 p 网络结构图如图 2 1 所示。 p 2 p 网络与传统网络的对比：p 2 p 打破了传统网络模式c s 模式，在p 2 p 网络中， 每个计算机在网络中地位都是平等的。每个节点既是信息的获取者还是信息的提供者。 首先，c s 模式在网络中是要依赖于中心服务器和门户网站，c s 模式下对中心服 务器的依赖较大，如果中心服务器崩溃，将要影响整个网络。c s 模式下的网络管理比 较容易，数据安全性和可靠性比较高。 其次，在p 2 p 网络中，每个节点都可以提供服务，提供信息，可以作为服务器节点 对整个网络提供服务，避免了c s 模式下的缺点，可以检索到整个网路的资源。 最后，在c s 模式下，由于计算机的软硬件的发展，终端已经有了很强的计算能力 和存储能力，这样在客户服务器模式下，客户端的能力被大大的浪费，有些资源一直利 用不到，中心服务器的压力却比较大。p 2 p 网络很好的解决了这些问题，所有的资源都 能够充分的得到利用。这两种模式的比较如图2 2 和图2 3 所示。 p 2 p 系统的特点：与其他网络模型相比，p 2 p 具有以下几个特点 8 。 非中心化( d e c e n t r a l i z a t i o n ) ：在网络中的所有节点上，分散着软件资源，硬件资 源和各种服务，通过节点间的信息交换来达到信息传递和实现各种服务，中间没有任何 中间商，避免了网络瓶颈的产生。p 2 p 网络有很好的扩展性和健壮性。 可扩展性：由于网络中没有中心服务节点，不存在中心节点带宽的瓶颈，p 2 p 网络 是可以无限扩展的。随着用户的加入，系统整体的资源和服务也在不断的增加，由于没 有中心服务器节点，不存在瓶颈问题，资源和服务能力不断的提高，更好的满足了用户 的需求。 一4 一 大连理工大学硕士学位论文 健壮性：系统是分布式的，服务和资源都分散在网络的各个节点上，一个节点失效 对整个网络的影响很小，整个网络在受到攻击的时候，所受到的破坏和影响也非常小。 p 2 p 网络在一部分节点失效时，能自动进行拓扑结构的重组，使网络中每一个节点能够 重新连通。p 2 p 网路节点可以自由加入和离开。每个节点都能够提供服务，不再依赖c s 模式下的中心服务器，具有很好的耐攻击性。 图2 2c s 网络模型结构图 f i g 2 2 c f i f f s e r v e rm o d e 图2 3p e e rt op e e r 模式 f i g 2 3 p e c rt op rm o d e 高性价比：随着科技不断进步，计算机软件资源和硬件技术不断发展，个人终端的 p 2 p 网络中t o p - k 查询算法的设计与实现 计算速度和存储能力不断的提高。而c i s 模式下，计算机终端的能力被忽略掉，没有充 分利用。p 2 p 模式，可以有效的利用终端的计算能力和存储设备，利用它们的软件资源 和硬件资源，提高整个网络的计算速度和存储能力。 隐私保护：在c s 模式中，所有的交互要经过中心服务器，中心服务器如果被攻击， 客户的隐私信息很可能被窃听和泄漏，造成用户巨大损失。p 2 p 网络很好的解决了这个 问题，因为它不需要中间商，通过节点间不断转发，匿名通信将通信的参与者隐藏起来。 在p 2 p 中，所有的节点都可以进行转发信息，大大提高了转发的速度和效率，更好的为 用户提供安全的服务。 负载均衡：在p 2 p 网络中，每个节点既提供服务又可以享受服务，减少了传统c s 模式下对中心服务器节点的依赖，资源分布在网络中的多个节点上，比c s 模式更好地 实现了整个网络的资源均衡，运算均衡和负载均衡。 p 2 p 的应用：p 2 p 网络的迅速发展，在众多领域获得了很大的成功，并且其软件用 户以爆炸式的速度增加，提供了以下的应用。 提供文件和其它内容共享：p 2 p 网络中，节点可以资源和服务共享，典型的系统包 括n a p s t e 一9 1 、g n u t e l l a t l o 】等。 基于p 2 p 方式的协同处理与服务共享平台：在p 2 p 网络中的用户利用网络共同完成 一个计算任务，共享软件和硬件资源。利用p 2 p 网络，客户端可以在线或者离线的发布 计算任务，分解这一任务，把不同的子任务分配到不同的节点上进行运算。比较著名的 协作系统包括m 硒和g r o o v e 系统。 内容存储应用：在p 2 p 网络中，每个节点都是平等的，都在获取服务的同时向其它 节点提供服务，并且将自己的一部分信息存储到其它的节点上，也可以为其它节点提供 存储服务。这种分布式的存储核心就是如何进行数据的定位，以及如何进行数据的复制、 更新、访问以及查找。这些研究主要有：p a s t 1 1 】以及o c e a n s t o r e 1 2 等。 p 2 p 系统的分类：按照p 2 p 网络的拓扑结构，可以将p 2 p 网络分成三种类型：集 中式p 2 p 拓扑结构，分布式p 2 p 拓扑结构和混合p 2 p 拓扑结构三类。 ( 1 ) 集中式p 2 p 拓扑结构 集中式拓扑结构是网络有一个节点存储整个网络的索引，包括所有节点的信息，以 及节点上存储对象的信息。当新节点加入到网络中时，新节点信息要在中心节点上面登 记。网络中所有节点都可以查找到中心节点。当一个节点发出查询请求时，把查询请求 发送给中心节点，中心节点收到查询请求后，在自己的索引表里进行查找，找到资源所 在的节点，并把这个节点信息返回给请求节点。请求节点接到消息后，与拥有资源的节 一6 一 大连理工大学硕七学位论文 点建立连接，并通过互相访问找到该资源。 ( 2 ) 分布式p 2 p 拓扑结构： 分布式p 2 p 网络拓扑结构是没有中心服务器的，每个节点的地位都是平等的，每个 节点既可以发出请求资源或者服务，也可以对外提供资源和服务，系统如图2 5 所示。 网络中的节点都会连接到网络中其它节点上，节点的地位都是平等的，它采取一种洪泛 的机制来定位资源的位置。节点把要请求的资源或者服务传递给它的邻居节点，邻居节 _ a f c h 争d o w n l o a d 图2 4 集中式p 2 p 拓扑结构 f i g 2 4 c e n t r a l i z e dp 2 pt o p o l o g ys t r u c t u r e 点在接到信息后，先查找自己是否能够提供这种资源和服务，如果找到就返回，否则继 续发给其邻居节点，设定一个阈值去控制查找节点的范围，一旦查找的邻居节点个数超 过阈值，则停止查找。对于请求的资源或者服务，有可能搜索到也有可能搜索不到。洪 泛机制要经历整个网络或者很大的范围才能找到结果。纯粹的分布式p 2 p 访问无目性， 造成网络带宽增大，查找效率不高，针对它的缺点，又出现了一种混合式的p 2 p ，使得 p 2 p 模式的系统结构更加合理和有效率。 上面所讨论的是非结构化拓扑p 2 p 系统，相对于非结构化拓扑中结点连接的随意 性，结构化拓扑为了实现有效的资源查找，对结点连接关系作了严格的限制，比如中心 型、超立方体型、层次、网状等结构。这些拓扑结构一般都通过分布式哈希表( d i s t r i b u t e d h a s ht a b l e ，简称d h t ) 来构建，利用d h t 将结点映射到一个结点标识空间，从而形成 特定的拓扑结构。c a n e l3 1 ，c h o r d e l4 1 ，p a s t r y 15 1 ，t a p e s t r y 16 1 ，s k i p n e t e l7 1 ，b u t t e r f l y 1 8 】 等都采用结构化拓扑，结构化拓扑可扩展性好，可以实现高效路由。在高度动态的网络 p 2 p 网络中t o p - k 查询算法的设计与实现 中，拓扑维护开销较大，基于d h t 的查询机制很难支持复杂查询。 ( 3 ) 混合p 2 p 拓扑结构 从上面可知，集中式和分布式的拓扑结构都存在一些问题，集中式存在中心索引节 点造成其抗攻击性比较差，其检索效率高。分布式的洪泛机制和随机转发机制，虽然不 图2 5 分布式p 2 p 拓扑结构 f i g 2 5 d i s t r i b u t e dp 2 pt o p o l o g ys t r u c t u r e - - - 争r c h 一争d o w n l o a d 存在中心索引节点，检索效率不高。考虑到节点的能力和带宽不一致，一些节点去承担 更重要的任务，另外一些节点由于能力有限，只保存信息和服务。混合p 2 p 拓扑结构系 统包含着三类节点： 用户节点：普通的节点就是用户节点，受限于其软件资源和硬件资源，用户节点不 具备特殊的功能。 搜索节点：一般是用户节点的父节点，搜索节点处理搜索请求，从它们的孩子节点 中搜索资源列表。 索引节点：对于连接速度快，内存充足的节点可以作为索引节点。索引节点保存可 以利用的搜索节点信息、搜集状态信息以及尽力维护网络的结构。 在混合节点中，搜索节点和索引节点被称为超级节点( s u p e r p e e r ) ，它们有很大 的带宽和很强的计算能力，它们在网络中承载着寻找路由，在其子节点搜索资源和信息 的重任，超级节点还负责管理其子节点的重任，系统如图2 6 。当某个节点发出请求信 大连理工大学硕十学位论文 息和服务的请求时，其父节点即超级节点接收到信息时，首先会在超级节点上进行查询， 超级节点维护其子节点的索引，可以知道请求的信息和服务到底在哪个节点上。这种混 合结构的p 2 p 系统中，超级节点的组织形式也有很多，如层次组织，超级立方体组织等。 以洪泛机制作为查找机制，由于超级节点的存在，大大减少了通信代价。超级节点要定 期更新子节点的信息，以满足查询时可以发现尽可能多的数据对象。 七一s e a r c h c - 争d o w n l o a d p e e r 图2 6 混合p 2 p 拓扑结构 f i g 2 6 h y b r i dp 2 pn e t w o r kt o p o l o g ys t r u c t u r e 2 2 t o p k 查询 t o p k 查询就是查找k 个最满足查询的结果。如果以评分来统计查询结果的话， t o p k 查询就是查找k 个最高值的对象。t o p k 查询分为聚合t o p k 查询和非聚合t o p k 查询，其主要区别就是是否应用到聚合函数。 t o p k 查询模型无论是在多媒体查询还是传统的数据库查询都有着非常好的应用。 用户并不希望查询出所有的精确结果，只需要排列出最符合查询的前k 个结果。t o p k 查询有点类似于我们平时用搜索引擎，每次查询时，对于提出的查询，都会返回最满足 查询的前t o p k 个页面，如果碰到用户感兴趣链接，查找的结果认为正确，就会去点击 返回的链接，如果没有找到，就回去翻阅下一页，还会找到满足查询的前t o p k 个页面， 直到用户满意或者用户放弃查询。搜索引擎很方便快捷，在日常生活中能够满足人们的 需要，在日常生活中，人们并不是关注满足查询的所有的结果，他关注很小一部分结果， p 2 p 网络中t o p - k 查询算法的设计与实现 或者通过t o p - k 结果的- d , 部分就能够启发输入更准确的查询条件。因此人们很满意这 种t o p - k 查询的方式，不但快捷而且节省了带宽。 最简单p 2 p 网络t o p - k 算法就是用户首先发出一个请求，这个请求以洪泛的方式进 行广播，采用的机制是随机转发，当邻居节点收到请求以后，邻居节点就会记录，证明 自己已经被访问过了，如果找到用户请求的资源或者服务，就在本地提供相应的资源或 者服务给请求节点。这种洪泛式查询方式消耗了大量的带宽，容易导致网络的堵塞，由 于p 2 p 网络中的节点的不确定性，造成了查找效率的低下和很慢的查询速度。 在p 2 p 系统中的t o p - k 查询通过筛选结果来减少网络的流量。在p 2 p 网络中t o p k 查询算法目标是实现低带宽消耗。假设在每个节点计算时间和成本可以忽略，沟通节点 间的成本占主导地位，那么查询响应时间主要取决于节点间交互的时间。本章主要介绍 了集中型p 2 p 聚合式t o p k 查询算法t a ( t h r e s h o l da l g o r i t h m ) 算法和t p u t ( t h r e e p h a s e u n i f o r mt h r e s h o l da l g o r i t h m ) 算法以及分布式p 2 p 的非聚合式的t o p - k 查询算法。 2 2 1 t a 算法 t o p - k 经典的算法就是由多个科研组独立开发的t h r e s h o l da l g o r i t h m 1 9 2 0 2 1 1 ，简称 t a 算法，算法思想如算法2 1 所示： 算法2 1t a 算法 输入：t o p k 查询 输出：t o p - k 集合中各对象及其聚集值 1 在所有节点上并行的进行顺序访问，根据查询，每次获得一个对象和它的评价值。 在其它所有节点上，随后随机的在其他节点中访问该对象，直至访问全部后，利用聚集 函数，计算该对象的聚集值。 2 定义v ( ) 是每个节点现在处理到已经出现最后一个对象，计算聚集的闽值 f = f ( v l ( o l 鲫) ，v 2 ( ) ，屹( ) ) 。 这个聚集阈值在每次出现新的对象的时候，都要重新 计算，厂为聚合函数。 3 定义节点新出现的对象为，这个对象一定是以前没有出现过的对象，如果的 聚集值比r 小执行结束。 请求节点分别向三个节点发出请求，通过t a 算法获得聚合t o p - k 值。表2 1 分别是 节点上的对象以及对象的评分值。该算法是正确的，不出现的对象，不可能比阈值更高。 大连理j i = 大学硕十学位论文 举个简单的例子：为检索t o p 2 ，首先顺序的检索第一个节点中排名在第一位对象0 ， 在其它节点中随机访问0 ，计算0 l 聚合值，y ( d 1 ) = m ( q ) + 屹( q ) + 鸭( d 1 ) = 1 0 + 9 + 1 = 2 0 。 阈值是排在第一位的所有对象的和= 1 0 + 1 0 + 1 0 = 3 0 ，因为2 0 刀) 进行编码，初始化位向量矿的每一个地址位的值为0 ，设有k 个相 互独立的哈希函数扛，。九。对于每一个数据对象s s ，位向量v 中对应于内 忽 矗 的地址位被置成1 ，如图2 9 所示。 p 2 p 网络中t o p - k 布询算法的设计与实现 根据b l o o m f i l t e r 这种机制，一个位置可能被多次置l ，但是能够真正起作用只有一 次，可能会导致原来不属于集合的元素被错误的判断属于这个集合，这个概率就被称为 “误称率”( f a l s ep o s i t i v ee r r o r ) 。在算法中，每次赋值到一个位置的概率为1 m ，而不赋 值的概率为1 1 m ，插入刀个元素后，某个位置仍然是0 的概率为： 咒：( 1 一土) 白，p 一鲁 ( 2 5 ) m 其中：m ：是位向量矿的长度； k ：是哈希函数的个数； 船：是已经装入的元素的个数即数据集合的大小。 检查一个元素b 是否是s 的成员的时候，如果在位向量矿中，第啊( 6 ) ，h 2 ( b ) ( 6 ) 位 均为1 的话就有可能发生“假通过的情况，所以假通过率厂可以用下式来计算： 1 _ b ， 厂= ( 1 一昂矿= ( 1 一( 1 一二) 切) ( 1 一p i ) 。= e k l n ( i - e - b l m ( 2 6 ) s 图2 9 使用四个哈希函数的b l o o m f i l t e r f i g 2 9 ab l o o m f i l t e rc o m p o s e db y4h a s hf u n c t i o n s 对于已经定下来的集合中元素个数f 和向量大小m ，怎么样得到最小的假通过率 厂，选择合理的h a s h 函数个数k 是很重要的。如果h a s h 函数的个数比较少，那么h a s h 过后得到的h a s h 值就比较少，要检查一个对象是否在这个集合中时，由于检查的机会 较少，比较不容易发现是0 的地址位，就更有可能产生假通过现象。如果使用更多的 h a s h 函数的话，得到的h a s h 值比较多，就容易发现是0 的地址位，假通过现象会减 少，但填充率增大。 求公式( 2 6 ) 的最小值，就是求g = 七h a ( 1 一e 嘲砌) 的最小值，对k 进行求导可得， 塑：l i l ( 1 _ e - | b l m ) 4 一k n 芝 ( 2 7 ) 大连理工大学硕士学侍砣文 显然当k = i n 2 x m n 的时候，g 和厂取得最小值，其最小值为： 1 f m = ( 1 一亡) ( 0 6 1 8 5 ) 刚” ( 2 8 ) z 这个时候b l o o m f i l t e r 的填充率为抛。通过以上可以知道，要想b l o o m f i l t e r 的假通 过率最小的话，填充率就是1 2 ，而h a s h 函数的个数，位向量的长度和数据集合的大小 的关系为：k = i n 2 m n 。 2 4 本章小结 本章回顾了p 2 p 的发展历程，阐述了p 2 p 的概念，详解了p 2 p 系统与传统网络的 区别，分析了p 2 p 系统的特点，并且介绍了比较经典的聚合t o p k 算法，t a 算法、t p u t 算法以及p 2 p 非聚合t o p k 算法。t a 和t p u t 是利用聚合函数对对象评价值进行累加， 找到累加和最大的k 个对象。非结构化p 2 p 系统中t o p - k 算法利用广播树的方法在每个 节点建立直方图，基于上一次查询在父节点存储的t o p k 向量信息，在其父节点上面用 先验概率的方法预估本次查询在每个节点的可能上限，从而能预先排除非法节点。最后 介绍了一种压缩编码技术，该编码技术应用在p 2 p 网络t o p k 查询中可以极大的减少带 宽的消耗。 p 2 p 网络中t o p - k 查向算法的设计与实现 3 混合非一致阈值聚合h n u t at o p k 搜索算法 1 9 9 8 年f i f a 世界杯网站自1 9 9 8 年4 月3 0 日到7 月2 6 日平均每分钟的访问超过 1 10 0 0 次，总计接受了超过l o 亿次访问。网站由分布在4 个不同地理位置的3 0 台服务 器构成，用户访问通过c i s c o 分布式控制器发送给不同的服务器处理。基于分布式w e b 服务日志，可以提出查询：目前在所有的服务器上最热门的网页是哪些? 表3 1t o p k 查询处理中的常用符号表 t a b 3 1 s y m b o lt a b l ef o rt o p - kq u e r yp r o c e s s i n g 含义 t o p - k 集合中元素的个数 任意节点发出的查询 在p 2 p 网络中超级节点f 在p 2 p 网络中节点f 在p 2 p 网络中的节点的对象f 对象，的属性f 查询g 作用在节点f 上对象d 的分值 聚合式t o p - k 查询中的聚合函数 查询g 作用在第d 个对象在所有节点上面的分值的聚合值v ( o d ) = 厂( v f ( ) ) 查询g 作用在第d 个对象在所有节点上面的分值的最大nm a x d = m a x ( v ，( o d ) ) 该查询是聚合式t o p k 查询，在集中式p 2 p 网络中，以一个超级节点发出查询，查 询在m 个子节点上存储的访问日志，最终检索出目前最热门的网页。表3 1 列出了本章 所常用的符号及含义。 定义3 1 单调聚集函数我们给定一个函数g ，这个函数满足即如果对于任意的 i ( 1 f 聊) ，都有x i x ：，则有g ( 而，而。x m ) g ( x i ，工2 。j 肼) 。最简单的一个单调聚集函 数就是做累加和。 定义3 2 顺序访问假设1 k f 一1 时，o k 排在o i 的前面，对于在节点上的任意节 点o ，被访问，对于o k ( 1 k f 一1 ) 一定已经被访问过。 竹t g皿。q毗州厂慨 大连理t 大学硕十学位论文 定义3 3 随机访问假设1 k f 一1 时，吼排在d ，的前面，对于在节点上的任意节 点d ，被访问，对于o k ( 1 k f 一1 ) 不一定被访问过。 定义3 4 聚集t o p k 查询聚集t o p k 查询是从p 2 p 节点中找出聚集值最高的k 个对 象的集合，即找出集合丁u 满足：iti - k 并且g o , t ，v o s u t ，有矿( d ，) v ( o 。) ， 其中，k 为给定t o p k 集大小。在本章中称r 为t o p k 集。 定义3 5 非聚集t o p k 查询非聚集t o p k 查询是从p 2 p 节点中找出非聚集值最高的 k 个对象的集合，即找出集合r u 满足：lt | - k 并且v o , t ，v o , u t ，有 m a x t m a x , ，其中，k 为给定t o p k 集大小。在本章中称丁为t o p k 集。 在p 2 p 网络中，节点上分别有不同的对象集合，每个对象d ，都有m 个不同的属性 a r t , , ( o j ) ，a t t r 2 ( o j ) a t t r , ( ) 。根据查询g 和对象的属性，计算出对象d ，在查询g 上的 分值u ( d ，) ，聚合t o p - k 查询和非聚合t o p k 查询计算方法如定义3 4 和3 5 所示。 3 1h n u t a 算法的基本思想和数据结构 t o p k 算法的衡量标准：一个是消耗的带宽，一个是返回数据的准确率。目前，t o p k 查询已经成为一个热点的问题。t a 算法族已经广泛的用于集中式网络环境中。t a 是一 个过于保守的算法，例如当你要查找t o p 1 0 的时候，t o p 1 0 0 的结果都已经找出来了， 采用一种随机查找策略，算法结束时间不确定。t p u t 由p e ic a o 提出，重新计算了阈 值，同时估计了对象的上限和下限范围，从而减少了信息交互。但是当阈值过小的时候， 传递过多的对象。近似t o p k 查询模型也有很多应用领域。这类方法在确定数据上进行 t o p - k 查询，返回近似的结果，为了提高查询的性能，用户也能接受。t h e o b a l d 2 8 】提出 了t a 的另一种近似变种，它引入一种模式，近似概率保证相关联t o p k 结果。 h n u t a 算法的执行的步骤是可选的，首先查询节点向所有节点发布查询信息，所 有节点按照标准在本地找到相应符合的值返回。像以往的t o p k 算法一样只考虑到对象 的值，满足一定值的对象上传，否则不上传。我们在考虑对象值的同时，还考虑到对象 的位置，通过对象位置和对象值的结合来统一考虑算法。 在所有的算法中，都是固定的阈值，使用固定的阈值是因为都假设节点中的对象在 网络中分布均匀，每个节点贡献大约相同个数的t o p k 对象。然而，在现实情况下，这 种假设并不成立，会存在一些热点节点，存在更高分值的对象。这些节点在对象分布上 面是非均匀分布的，在一些节点上的对象有较大的分值分布，在其它节点上可能具有较 小的分值分布。方便起见，我们称呼这些节点为热节点和冷节点，大部分的t o p k 结果 来自于热节点，因此不应该每个节点都应用同一个阈值。 p 2 p 网络中t o p - k 夯询算法的设计与实现 如果超级节点发出一个t o p - k 查询，我们就是用累加和公式3 1 ，y ( q ) 就是对象q 部分和： 矿( 。，) = 窆v ，( 。，) ( 3 1 ) 当t o p - k 算法执行的时候，对象列表中对象和它们的评价值就被传送到超级节点。 节点歹报告对象与对象值就被称为s e t j ，如果叱没有出现在