（计算机软件与理论专业论文）基于对等网络的文档搜索技术.pdf

中文摘要 对等计算( p 2 pc o m p u t i n g ) 作为- 7 十全新的分布式计算模式越来越多的受到学 术界和工业界的共同关注。由于p 2 p 系统具有良好的可扩展性、鲁棒性和信息 可用性，因而被认为是未来i n t e r n e t 应用的前沿技术之一。同时，由于互联网的 出现，人们迫切的需要从网上的海量数据中进行有效的文本检索。基于对等网 络的文档检索系统由于其分布计算的性质和良好的扩张性，可以增强系统检索 大规模文本的能力，特别适合互联网上不断增长的信息检索的需要。 目前，学术界提出了一些在对等网络进行基于关键词查询的文本检索系统， 但是这些系统存在着消耗带宽过多，查询执行时间较长，搜索准确率不高和查 询负载不平衡等缺点。针对以上的问题，我们提出了一种新的在d h t 网络中进 行文档发布和检索的方法，对于网络中节点选择和负载平衡方法进行了研究， 并开发了两个基于对等网络的信息检索系统。本文的主要贡献如下： 提出了k e y n o t e ，一种新的基于c h o r d 网络的信息检索平台。k e y - n o t e 采用全新的t e r m n o d e 的信息发布方法，大大减少了带宽消耗和存储 代价。模拟实验证明，k e y n o t e 可以应用至u i n t e r n e t 规模的信息检索， 并且成功解决了对等网络中的文档全局排序的问题。 提出了两种简单但是非常有效的基于d h t 网络的节点选择方法。实验证 明，这两种节点选择的方法可以保证大多数和查询相关的文档可以通过访 问网络中- - 4 , 部分节点来获得。设计了一种基于c h o r d 的负载平衡方法， 这种方法能够保证在o ( 1 0 9 n ) 的路由跳转数内实现某个节点上面关于某个 关键词的负载平衡。 开发了两个基于对等网络的信息检索系统，包括基于非结构化对等网络的 信息检索系统b s e a r c h 和基于d h t 对等网络的消息检索系统s i p p e r 。 关键词：对等计算，文本检索，负载平衡，t o p - k ，关键词查询 分类号：t p 3 1 1 a b s t r a c t r e c e n t l yp e e r t o - p e e r ( p 2 p ) s y s t e m sh a v ee m e r g e da 8an e wd i s t r i b u t e dc o m - p u t i n gp a r a d i g m lw h i c hh a sa t t r a c t e dm o r ea n dm o r ea t t e n t i o nf r o mt h ea c a d e m i c a n di n d u s t r yc o m m u n i t y c o m p a r e dw i t ho t h e rn e t w o r ka r c h i t e c t u r e s ，p 2 ps y s t e r n sh a v ei t su n i q u ea d v a n t a g e ss u c ha ss c a l a b i h t ya n dr o b u s t n e s s o nt h eo t h e r h a n d ，t h ee m e r g e n c eo fi n t e r n e ti m p o s e sac h a l l e n g ef o re f f i c i e n ti n f o r m a t i o nr e t r i e v a lo nl a r g e s c a l e dt e x t t h ec o m b i n a t i o no fp 2 pc o m p u t i n ga n di n f o r m a t i o nr e t r i e v a lc a s tl i g h to i lt h e s o l u t i o nf o rl a r g e s c a l e dt e x ts e a r c h s of a r ，al o to ft e x ts e a r c hm e t h o d si np 2 p n e t w o r k sh a v eb e e np r o p o s e d h o w e v e r ，t h e s em e t h o d ss u f f e rf r o ms o m ep r o b l e m s s u c ha sl a r g eb a n d w i d t hc o n s u m p t i o n ，h i g hq u e r ye x e c u t i o nl a t e n c y , l o ws e a r c h a c c u r a c ya n du n e v e nl o a dd i s t r i b u t i o n t oa d d r e s st h e s ep r o b l e m s ，w ei n v e s t i g a t e t h ec h a l l e n g e sf o rl a r g e s c a l e dt e x ts e a r c hi np 2 ps y s t e m sa n dm a k et h ef o l l o w i n g c o n t r i b u t i o n s ： w ep r o p o s ek e y n o t e ，an o v e lk e y w o r ds e a r c hs y s t e mo v e rc h o r do v e h a y n e t w o r k su s i n gt e r m n o d ei n f o r m a t i o np u b l i c a t i o nm e c h a n i s m ，w h i c hc a n g r e a t l yr e d u c eb o t hc o m m u n i c a t i o na n ds t o r a g ec o s t w ea l s op r o p o s ea s o l u t i o nf o rt h eg l o b a ld o c u m e n tr a n k i n gp r o b l e mi np 2 pn e t w o r k s t w os i m p l em e t h o d sf o rn o d es e l e c t i o na r ep r o p o s e d w h o s ee f f e c t i v e n e s si s p r o v e db yt h ee x p e r i m e n t a lr e s u l t s al o a db a l a n c i n ga l g o r i t h mi sp r e s e n t e d f o rt h ec h o r do v e r l a y , w h i c hc a ng u a r a n t e et h a tt h el o a db a l a n c i n go fe a c h h o tt e r mo no n eg i v e nn o d ec o u l db ea c h i e v e di no ( 1 0 9n ) r o u t i n gh o p s ( n i st h en u m b e ro fn o d e si nt h en e t w o r k ) w ei m p l e m e n tt w od o c u m e n ts e a r c hs y s t e m so np 2 pn e t w o r k s i n c l u d i n g o n es y s t e mb a s e do nb e s t p e e ra n dt h eo t h e rs y s t e mb a s e do nc h o r d k e y w o r d s ：p 2 p ，t o p - k ，t e x ts e a r c h ，l o a db a l a n c i n g ，k e y w o r ds e a r c h 1 1 图目录 2 ，1 b e s t p e e r 平台 2 2 c h o r d 系统 3 1 传统的d h t 网络中关键词搜索方法 3 , 2 k e y n o t e 中的信息发布机制 4 1 在2 0 0 0 个节点的网络中t o p k 的搜索性能 4 2 网络规模的大小对搜索性能的影响 4 3 在c h o r d 系统中的搜索树 4 4 两种负载平衡算法的性能比较 5 1 b s e a r c h 节点的内部构架 5 2b s e a r c h 的搜索结果界面， 5 3 b s e a r c h 的文档共享界面 5 4 在b s e a r c h 中的邻居选择策略 5 5 s i p p e r 系统的网络构架 5 6s i p p e r 系统节点的内部构架 57s i p p e r 系统主界面 5 8s i p p e r 系统搜索返回界面 v l 0 m m 媳 s j 踮耵 如姐甜诣町勰蜉 第一章 引言 1 1 1 研究背景 近几年来，随着万维网和大规模存储设备的出现，个人电脑和i n t e r n e t 上存储 的数字信息呈指数级增长。如何有效的从海量数据中获取人们需要的信息，已 经成为迫切需要解决的热点问题。信息检索( i n f o r m a t i o nr e t r i e v a l ) 正是解决 这个问题的一个关键技术。目前，信息检索技术已经成为学术界和工业界共同 关心的热点问题。国际学术会议如s i g i r 和t r e c 已经成为世界上信息检索研 究学者的交流平台。一些商业公司提供的搜索引擎，如g o o l g l e 6 】，百度 2 】，雅 虎1 0 1 等已经成为人们浏览互联网不可缺少的工具。 对等计算f p e e r - t o - p e e rc o m p u t i n g ) 作为一种全新的分布式计算模式越来越 多的受到学术界和工业界的关注。对等计算同以往的客户机服务器构架不 同，它的最大优点是良好的扩张性一系统中节点越多，系统的处理能力越 强。一一些基于非结构化对等网络的文件共享软件女i n a p s t e r 9 ，g n u t e l l a 5 1 ，b i t t o r r e n t 4 等，已经成为互联网上流行的软件。学术界也提出了一些结构化的对 等计算网络，女 i c h o r d 3 5 和c a n a l l 等。 构建对等计算的环境下的信息检索系统，是一个既有现实意义又有挑战性的 问题。一方面，跟集中式的信息检索系统相比，对等计算系统下的信息检索系 统由于其分布计算的性质和良好的扩张性，可以增强系统检索大规模文本的能 力，特别适合因特网上不断增长的信息检索的需要。另一方面，由于对等计算 系统的自治性和动态性等特点，如何在对等计算系统中进行有效的文本索引和 查询处理，也是研究者面临的新的挑战。 本文对于如何在结构化和非结构化的对等计算网络中进行有效的信息检索， 进行了深入的研究并且开发了原形系统。作为本文的组成部分，我们先对对等 计算和信息检索的概念和应用先做一简单介绍。 引言 1 1 1 对等计算 对等计算( p e e r t o p e e rc o m p u t i n g ，简称p 2 p ) ，自从2 0 0 0 年以来迅速成为学 术界和工业界共同关注的热点。跟传统的c s 构架的网络不同，对等网络中的 每个节点( p e e r ，如用i n t e r n e t 连接起来的p c ) 都拥有对等的功能与责任，即 每个节点既可以充当向其他的节点提供数据或服务的服务器，又可以是享用其 他节点提供的数据或服务的客户机。不过关于p 2 p 确切的定义，目前还没有统 一的标准。i n t e l 给p 2 p 的定义是“通过系统间的直接交换所达成的计算机资源 和信息的共享，这些资源和服务包括信息交换、处理器时钟、缓存和磁盘空间 等”；i b m 则给p 2 p 更广泛的定义，把它看成由互连协作的计算机构成的系统 并具有若干特性。我个人认为，p 2 p 有以下几个特征，使它区别与其他计算模 式： 1 节点对等性。基于服务器客户端的网络中，必须有一台机器作为提供 数据和服务的服务器。在完全分布式的对等网络中，根本没有服务器这 个概念，或者说网络中的每个节点既是服务器又是客户端。介于集中式 的网络和完全分布的对等网络之间，混和式的对等网络中有一些超节点 ( s u p e r p e e r ) ，也向网络中的普通节点提供服务。 2 ，网络动态性。对等网络中的任何节点可以在任何时候随意加入网络，也可 以随意退出网络。而在客户端服务器架构的网络中，服务器通常要2 4 d 时不间断工作来向客户端提供可靠的服务。网络动态性也是p 2 p 网络区别 于一般的分布式系统的一个重要特征。在分布式系统中，由于各个节点有 其各自相对固定的任务和分工，所以往往不允许节点的随意加入和退出。 而在对等网络中，节点的任意退出和加入，不会对系统的性能造成很大影 响。 3 大规模性。在传统的分布式系统中，节点数量一般是几百个，但是 在p 2 p 网络中，节点数目可以达至l j i n t e r n e t 级别，网络规模远远大于分布式 系统。 4 节点自治性。自治性主要包括两个方面：一个是存储和处理事务的自治 性，节点可以自主地决定本地文件的共享范围( 哪些文件可共享) 以及共 享权限等，并且主要关心本地事务；另外一个方面是选择邻居( 直接相互 联接的两个节点定义为邻居) 的自治性，即节点可以选择哪些节点成为自 己网络中的邻居，并且可以规定邻居的数目。在非结构化的对等网络中， 节点的自治性表现的比较明显，但是在结构化的对等网络中，节点的自治 性有所破坏。如在基于c h o r d 3 5 】的对等网络中，节点必须存储些来自与 2 引言 其他节点的数据， 节点自己决定。 p 2 p 系统的以上特点 个潜在的优势： 并且每个节点选择哪些邻居由c h o r d 协议决定，并非由 决定r 对等计算和其他计算模式相比，至少有以下几 1 良好的可扩张性。对于p 2 p 系统来说 新的存储空间，计算能力和网络带宽 资源越丰富，处理能力也越强。 每个新加入的节点都会给系统增加 应此，网络中的节点越多，系统的 2 良好的鲁棒性。因为在对等网络中没有集中式机制，p 2 p 系统不会出 n c s 模式存在的单点出错( s i n g l e - p o i n tf a i l u r e ) 。而且，由于系统中的 每个节点同时有多个邻居节点，某个或某些节点的失败或离线不会严重影 响系统中的其他节点。 3 负载平衡性。在对等网络里面，有一些节点处理能力比较强又经常处于空 闲状态，我们可以用负载平衡算法给这些节点分配更多的任务；反之如 果某些节点处理能力比较弱来不及处理任务，我们可咀把这些任务分配给 i 其他空闲的节点。在对等网络中实现负载平衡算法，可以最大程度的提高 系统的资源利用率。 由于p 2 p 系统韵以上优点，到目前为止，已经有大量的基于对等计算模型的 软件系统应运而生。其中包括早期的m p 3 的音乐共享软件f r e e n e t 1 4 ，n a p s t e r 9 1 ，g n a t e l l a 5 ： 到现在流行的k a z a a 7 ，b i t t o r r e n c 4 等。 在学术界，对等网络的研究也取得了大量的研究成果，包括一些和对等网络 底层平台有关的，如c h o r d 3 5 1 ，c a n 3 1 ，t a p e s t r y 4 0 ，p a s t r y 3 3 ，b e s t p e e r 3 等， 以及在对等网络平台上面的技术应用如d h t 2 7 ，o e e a n s t o r e 2 4 j ，p i a z z a 2 1 等 等。 1 _ 1 2 信息检索 何为信息检索? 按照现代信息检索1 1 1 的定义，信息检索( i n f o r m a t i o n r e t r i e v a l ) 包括信息的存储、组织、表现、查询、存取等各个方面，其核心为 信息的索引和检索。一个典型的信息检索的例子就是用户利用互联网上面的搜 索引擎查找感兴趣的信息。用户首先要把他感兴趣的信息转换为几个关键词， 然后信息检索系统就把用户可能感兴趣的文档返回给用户。广义上来说，信息 检索包括文本检索和多媒体检索，但是由于本文只讨论文档检索，所以信息检 索，文档检索和文本检索这几个概念在本文中表示同样一个意思。 3 引言 耍正确理解信息检索的概念，必须区分数据检索和信息检索这两个概念的不 同。数据检索主要解决的是哪些数据满足了用户发出的盘询，但是往往不能满 足用户的信息需要。而信息检索更关心的是检索用户真正感兴趣的关于某个主 题的信息，一个数据检索系统的典型例子是关系数据库管理系统里面的查询系 统。数据库系统可以精确的返回那些满足用户用关系代数语言表达的查询的数 据，但是对于如何返回用户感兴趣的基于某个主题的信息却显得无能为力。信 息检索系统却可必“理解”用户的查询和文档里面的内容，然后根据文档和查 询的相似度( r e l e v a n c e ) 将文档进行排序，并将用户感* 趣的信息返回给用 户。 为了计算文档和查询的相似度，学术界提出了很多信息检索的模型，包括向 量空间模型，布尔模型，概率模型等等1 1 。其中向量空问模型是比较主流的 模型，也是本文采用的是模型。在向量空间模型中，所有的文档都用向量来表 示，每个在文档里面的单闭都对应文档向量里面的一个权重。具体来说，一个 单词乜在文档d j 里面的权重定义为： ”叫= 蔫刈。9 笔 ( 1 1 ) ”叫5 忘考蒜刈。9 面 ( 1 1 ) 其中f r e q i + j 是单词在文档屿里面出现次数，而d 2 a x f r e q l 是这个文档里面出 现最频繁的那个单词的出现次数是系统里面文档的总数，而m 是含有硅这 个单词的文档数目。用户输入的查询也是用相似的向量模型来表示。给定了 个查询g 和一个文档西，我们就用q 和画这两个向量夹角的c o s i n e 值来表示查询和 文档之间的相似度： _ s i m ( 吒，g ) = c o s ( d j ，q ) = i 黑 ( 12 ) l 嘭 “jg l 一个完整的信息检索的步骤至少包含以下3 个步骤：f a ) 系统对文档库里面所有 的文档进行索引，建立索引的目的是为了加速搜索大规模文档的过程，目前比 较流行的索引结构是倒排表 1 l 】，( b ) 系统通过用户界面把用户的需求变成可执 行的查询，( c ) 系统执行查询操作，返回用户感兴趣的文档集，并根据相似度对 返回的文档进行排序。 1 _ 2 研究动机和本文贡献 虽然目前互联网上面的搜索引擎，立 i g o o g l e 和b a i d u 等，已经能够为用户提 供比较可靠和满意的搜索服务，但是由于对等网络良好的可扩张性和鲁棒性， 如何在对等网络下构建不依赖与中央服务器的搜索引擎是一个非常有价值的研 究课题a 在对等网络的搜索系统中，用户通常只会对和自己输入的查询最相 4 引言 关的t o p e 的结果感兴趣，而这个 = o p - k 的结果通寓只存在一小部分节点中( 项 多七个节点) 。如何在对等嘲络中把和用户输入的查询匹配的- - $ 部分节点选择 出来，是构建基于对等网络的信息检索系统面临的。个挑战。 到现在为止，学术界已经提出了一些在d h t 的对等网络中进行信息检索的方 法，但是这些方法需要消耗很大的存储空间和网络带宽。当对等网络的规模变 大的时候，网络带宽的消耗和执行查询的延迟成为制约对等网络搜索系统的性 能的瓶颈。如何在对等网络中以较小的存储代价和带宽消耗采构建信息检索系 统又是我们面i 陶箝一大挑战。 现存方法的第三个问题是对等网络中节点的查询的负载不是均衡分布的，即 使对等阿络采用的是随机的d h t 方法。如何在对等网络中实现负载平衡，是构 建对等网络的信息检索系统必须要解决的一个问题。 现存方法还有一个有待解决的问题是，文档的全局排序阅题。我们知道，节点 在本地计算文档的相似度是基于本地的统计信息，而在对等网络中每个节点 上面的统计信息是不一样的，这样每个节点计算出来的相似度只是本地的相似 度不能用来进行全局的排序，如何构建支持文档全局排序的信息检索系统， 也是在对等网络中优化搜索性能面临的一个挑战。 针对以上问题，我们展开相关研究工作，并做出了如下的贡献： l 我们提出了k e y n o t e ，一种新的基于c h o r d 网络的信息检索平台。k e y - n o t e 采用会新的t e r m - n o d e 的信息发布方法。跟传统的方法相比， 我们这种方法可以人大减少带宽和存储代价，并且通过模拟实验证 明，k e y n o t e 可以应用到i n t e r n e t 规模的信息检索。同时，k e y n o t e 中 的信息发布机制和崔询处理过程，有效的解决了文档的全局排序问题。 2 我们提出了两种简单但是非常有效的基于d h t 网络的节点选择方珐。实验 证明，这两种节点选择的方法可以保证大多数和香询相关的文档可以通过 访问网络中一小部分节点来获得。 3 我们提出了一种基于c h o r d 的负载平衡方法，这种方法能够保证在0 0 0 9 n ) 的 路由跳转数内实现某个节点上面关于菜个关键词的负载平衡。 4 我们开发了两个基于对等厢络的信息检索系统，包括基于非结构化 对等网络的信息捡索系统b s e a r e h 和基于d h t 对等网络的消息检索系 统s i p p e r 。 1 3 本文组织 下章将介绍相关的工作。主要包括对等计算网络平台和在对等网络上面己 5 经提出的信息检索方法。第三章介绍我们提出的基于d t 网络的信息检索平 台k e - y n o t e 。第四章介绍d h t 网络中的节点选择方法和在c h o r d 网络中的负 载平衡方；! 毒。第五章主要介绍了我们开发的基于对等网络的信息检索系统，包 括基于b 蹈t p e e r 平台的信息检索系统b s e 舡c h 和基于d h t 对等网络的消息检索系 统s i p p e r 。籀六章是对当前1 作的总结。 6 第二章 相关工作 这一章将介绍和本文相关的工作，主要包括对等网络平台和对等网络中文本 搜索技术两个方面。关于节点选择和负载平衡的相关工作，我们将在第四章中 做介绍。 2 1 对等网络平台介绍 对等网络根据节点在应用层上面的组织结构，可以大致分为非结构化对 等网络( u n s t r u c t u r e dp 2 pn e t w o r k s ) 和结构化的对等网络( s t r u c t u r e dp 2 p n e t w o r k s ) 两大类。下面针对这两大类的对等网络做相关的介绍，对于非结构 化的对等网络我们重点介绍b e s t p e e r 平台 3 】，对于结构化的对等网络我们重点 介绍c h o r d 3 5 。 2 1 1 非结构化对等网络 非结构化的对等网络是较早出现并有很多应用的一种对等网络。在这种系 统中，节点的组织比较松散，在应用层上面节点可以和任意其他节点相连接。 相对于结构化的对等网络，非结构化的对等网络具有更强的自治性，并且更 容易实现，动态性也更明显，应此具有这种特性的网络也被称为即兴网络( a d h o cn e t w o r k l 。正是由于网络结构比较松散，所以在非结构化的网络中进行搜 索一般通过广播，多播或者依赖于索引服务器来实现。根据对索引服务器的依 赖程度，非结构化的对等网络又可分为集中式的( c e n t r a l i z e d ) 、全分布的( f u l l y d e c e u t r m i z e d ) 和混和式的( h y b r i d ) 。在集中式的对等网络中，用户首先查询系 统中存在的单个索引服务器，然后根据服务器上面的索引内容，到网络中其他 节点中搜索自己感兴趣的文件。n a p s t e r 9 就是属于集中式对等网络的一个典 型例子。集中式对等网络的缺点是容易发生单点故障( s i n g l e p o i n tf a i l u r e ) ，一 7 相关工作 旦系统中索引服务器出现问题，整个网络就不能提供搜索服务。而在全分布的 对等网络中，不存在任何的索引服务器，搜索通过广播或者多播来实现。全分 布式网络的典型例子就是g n u t e l l a 5 1 。虽然不依赖于索引服务器，广播和多播 可以说成是一种泛滥( f l o o d i n g ) 搜索，通常要耗费大量的网络资源。混和式的对 等网络中既存在多个超级节点( s u p e rp e e r ) ，也存在很多一般的节点，并且每 个一般节点必然属于某个超节点管辖。超级节点通常向一般节点提供索引或 者其他查询服务。混和式的对等网络集台了集中式和全分布式对等网络的优 点，b e s t p e e r 3 就是混和式的一个典型代表。 由于会在第五章介绍我们开发的基于b e s t p e e r 的信息检索系统，我们先在这 里简要介绍一下b e s t p e e r 平台。 b e s t p e e r 平台 b e s t p e e r 是我们和新加坡国立大学一起开发的混和式的对等网络平台。 b e s t p e e r 计算模型由两类实体组成：大量的一般对等节点和少量的位置独立的 全局名称查找服务器( 1 0 c a t i o ni n d e p e n d e n tg l o b a ln a m e sl o o k u ps e r v e r ) ，如 图2 1 所示。 图2 1 ：b e s t p e e r 平台 每个节点运行一个b e s t p e e r 的实例，共享一部分数据，并且可以访问与其直 接相连的那些节点的共享数据。以图2 1 为例，由于节点a 直接与节点b 直接相 连，所以节点a 可以访问节点b 的共享数据。如果节点a 要访问节点c ，则必须 通过节点b ，因为节点a 和节点c 没有直接相连。但是在b e s t p e e r 网络中，数据 的下载是独立于对等网络平台的，也就是说节点c 通过节点b 收到来自节点a 的 查询要求后，可以直接和节点a 建立连接传输数据，不需要把数据沿着查询路径 的反方向返回给查询的发起者。 8 相关工作 考虑到节点的动态性，节点可能会在不同地方登录到对等网络中，造 成节点的i p 地址可能发生变化。l i g l o ( 1 0 c a t i o ni n d e p e n d e n tg l o b a ln a , n l e s l o o k u p s e r v e r ) 服务器就是为了解决这个问题而引入的。服务器的主要功能是为 节点分配一个全局唯一的i d ，我们称之为b p i d ( b e s t p e e ri d ) ，b p i d 用来唯 一的标示一个节点，而不管它的i p 地址。b p i d 由两部分组成( l i g l o i d ，n o d e i d ) 其中l i g l o i d 是l i g l o 服务器的i p 地址，n o d e i d 是l i g l o 服务器为节点分配 的唯一的标示，这样就能区分不同的l i g l o 服务器分配的b p i d 不会重复。 b e s t p e e r 是第一个将移动a g e n t 技术和p 2 p 技术结合起来的p 2 p 系统。通过移 动a g e n t ，b e s t p e e r 不但可以共享文件和数据，而且可以共享计算资源和其他有 意义的信息。比如，在图2 1 中，节点a 能够把一个含有数据和代码a g e n t 发送到 节点b ，让节点b 执行a g e n t 里面的代码，并把执行结果返回给节点a 。更重要的 是，利用a g e n t 技术，节点可以在b e s t p e e r 网络中采集一些重要的信息，比如网 络中其他节点共享数据的统计信息，而且可以在离线的状态下完成。利用这些 重要信息，节点可以选择网络中哪些节点成为自己的邻居或者哪些节点可以提 供更好的服务。 b e s t p e e r 还支持多粒度数据共享技术和网络自配置策略，有兴趣的读者可以 参考【3 o 2 1 。2 结构化对等网络 不同与非结构化的对等网络，在结构化的对等网络中，节点的组织遵守严 格的特定规则，而且资源( 比如共享文件) 被精确的分配到指定的位置。 女f l c h o r d 3 5 $ g c a n 3 1 系统都是根据d h t 2 7 映射确定每个节点的i d ，然后根据 某种特定的规则把节点放置到逻辑表示空间中去。还有一些结构化的对等网络 平台，如p a s t r y 3 3 】和t a p e s t r y 【4 0 】则是利用p l a x t o n 算法 3 0 的变形来构建对等网 络。 结构化对等网络的优点是由于资源和位置之间存在某种对应关系，所以能够 保证查询和路由的高效率，而且系统性能一般有理论上的保证。但是，结构化 的对等网络也有其缺点，比如节点的自治性比较差，节点不能自由决定存储哪 些内容和选择哪些邻居；另外，当网络的动态性比较明显的时候，也就是网络 中节点的退出和加入比较频繁的时候，系统的性能就会收受到很大的影响。 由于第五章介绍的信息检索系统是基于c h o r d 对等网络的，为了方便读者理解 其中的细节，所咀在这里先对c h o r d 系统做一个简单的介绍。 9 塑茭三堡 一 c h o r d c h o r d 是基于d h t 的结构化p 2 p 网络的一种典型代表。在c h o r d 系统中，所有 的节点和数据项都拥有由一致性啥希产生的唯一的i d 。这些i d 被分配到一个 从o 到2 m 一1 的一维环型空间座标上，其中m 是c h o r d 系统的一个参数，由它决 定c h o r d 环的空间大小。图2 2 显示了一个含有6 个节点( o ，1 ，4 ，5 ，8 ，1 2 ) 的c h o r d 环， 并且这个c h o r d i 环的系统参数1 1 1 等于4 。 图22 ：c h o r d 系统 在c h o r d 环中，节点和数据项的对应规则每个数据项存放在c h o r d 环中在顺 时针方向第一个等于或者超过这个数据项i d 的节点中。比如，在图2 2 中， 节点o 负责数据项1 3 ，1 4 ，1 5 ，0 ，而节点1 只负责数据项1 。每个节点( 用p 表示 其i d ) d 2 有m 项记录，这m 项信息被称为节点p 的f i n g e r 表。每个f i n g e r 袭中记 录三个信息，即开始( s t a r t ) ，间隔( j n t e r v 出) 和后继节点( 8 u c c e s s o r ) 。具体来说，在 节点p 上的第i ( 1 i m ) 项记录里面的“s t a r t ”存放地址2 i - - l l l i n t e r v a l ”存放地址 范围( p + 2 一1 ) r o o d2 m ，( p + 2 t ) r o o d2 ”) 】，而“s u c c e s s o r ”里面记录在c h o r d 环 中顺时针方向超过p 至少2 t 一1 的第一个节点的i d 。在图2 2 中，节点0 的n n g e r 表中 有4 个记录，每个记录里面分别存放后继节点1 ，4 ，4 ，8 。其中第三个记录，记录了 开始4 问隔4 ，8 ) 和后继节点4 。 为了查找某个k e y ，每个节点( 用b 表示其i d ) 只要把查询的消息发给它f i n g e r 表 中离自己最远的s u c c e s s o r ( 用r 表示) ，并且满足只( 弓，k e y ) 。这个过程一直进 行下去，直到k e y 位于某个节点和这个节点第一个后继节点之间，这意味着这个 后继节点就是存放这个k e y 的目的节点。在图2 2 中，如果节点0 想要查找k e y1 1 ， 则路由的路径是0 8 1 2 1 0 相关工作 2 2 对等网络中的文本搜索技术 随着对等网络的兴起，人们对于对等网络中的信息检索技术的研究也取得了 不少成果。下面分别就非结构化和结构化对等网络中的信息检索技术的相关研 究成果做一简单介绍。 2 2 1 非结构化对等网络中的文本搜索技术 p l a n e t p 1 5 是一个较早的基于非结构化的对等网络的信息检索系统。它 利用b l o o mf i l t e r 来概况每个节点上面存储的内容并且把这些摘要信息通 过g o s s i p i n g 算法发布到整个对等网络中去。基于这些摘要信息，每个节点用 一种简单的t f x l d f 排序算法来选择对等网络中与查询最相关的那些文档。但 是，由于存储在b l o o mf i l t e r 里面的摘要信息不是非常精确的，检索的正确率不 能够被保证。而且，由于g o s s i p i n g j i g 法的内在缺陷，p l a n e t p 的可扩展性不是非 常好，不能充分发挥对等网络的优越性。 在文献 2 6 l 中，c m u 的l u 等提出了在混和式的非结构化对等网络中进行基于 内容的资源选择和文档检索的方法。在这个系统中，每个叶子节点( 即一般对 等节点) 相当于一个数字图书馆，提供全文的搜索服务；而每个目录节点( 即超节 点) 则利用资源选择的方法把查询路由到合适的节点。尽管这种方法通过资源选 择减少了网络中不必要的消息数目，但是由于非结构化网络的缺点，搜索的查 全率( r e c a l l ) 往往不能够被保证。 s e t s 1 2 是斯坦福大学提出的对等网络中基于机器学习和s o c i a ln e t w o r k 理论 的信息检索的平台。该系统的基本思想是把参与的节点按照主题来放置到对等 网络中去，使得具有相似内容的站点处于网络中相近的位置。同时，每个节点 除了和自己主题相近的邻居外，还有- - d 部分l o n gd i s t a n c e 连接指向其他主题的 节点。当一个查询发起以后，首先利用全局路由找到和查询相近的主题网络， 然后在这些主题网络里面再利用局部路由搜索和查询相关的结果。s e t s 的优点 是只需要访问一小部分网络就可以获得比较高的查全率，缺点是构建主题网络 和更新主题网络的代价比较大。 在文献f 2 9 1 中，新加坡国立大学提出了一种在即兴网络中相似度查询问题的解 决方案。在这个方法中，当节点收到某个新的查询以后，如果发现节点中已经 运行了类似的查询，就把新的查询“冻结”f f r o z e n ) 在节点上，不再向网络中传递 这个查询，并且用和这个新查询类似的那个查询来返回结果。通过这种方法， 网络中的消息数量就会大大减少，并且网络的延迟时间也会变短。这个方法的 前提是用户必须经常提交类似的查询，所以当用户查询变化比较快的时候，系 统的性能就会有所下降。 相关工作 2 2 2 结构化对等网络中的文本搜索技术 b a l k e 等在文献f 3 7 1 里面提出了一种在h y p e r c u p 结构的混和对等网络0 0 t o p - k 检索的解决方案，旨在减少数据通讯量和保证搜索结果的正确性。当一个查 询第一次发起的时候，系统就把这个查询通过丑o o d i n g 的方法发布到整个对等 网络中去进行处理。当查询处理完毕，每个超节点就为这个查询保留了路由信 息，从而方便以后处理类似的查询。这种方法的局限是依赖与对等网络中的超 节点，因此不适合应用到完全分布的对等网络。 p s e a r c h 3 7 是- - 个基于c a n 的对等网络信息检索系统。它利用潜在语义索 引f l s i ) 把文档向量降维成c a n 空间里面的座标，然后把文档定位至u c a n 空间 里面的节点，这样能够保证相似的文档放置在c a n 空间相近的节点上。当用 户发起了一个查询，系统先把这个查询转换成向量并且定位至u c a n 空间里面 负责这个查询向量的节点，然后把这个查询继续发送到这个节点的相邻节 点。d s e a r c l l 具有很高的查询准确性，并且它的搜索算法保证了每个查询只需要 访问系统中很小一部分节点。但是，由于对等网络的动态性，p s e a r c h 必须定时 重新计算潜在语义索引来保证搜索的准确率。系统能否承受这个更新代价，也 是一个需要考虑的问题。 在d h t 的对等网络中进行关键词的搜索3 2 1 是对等网络中信息检索研究的热 点问题。在这种方法中，当一个节点发布文档的时候，它按照文档里面每个 单词的哈希值把单词在文档里面的m e t a d a t a ( 比如单词在文档里面的词频) 和文 档i d 发布蛩j d h t 网络中对应的节点去。当用户发起了一个含有多个单词的查询 以后，关于单词在每个文档的m e t a d a t a 必须从一个节点传输到另外一个，从而 实现执行关键词的连接( j o i n ) 操作。这种方法的缺点是，由于关键词连接操作必 须传递网络中含有关键词的所有文档的列表，所以当网络中存储了很多文档的 时候，这种方法就会消耗很大的存储代价和网络带宽。 到现在为止，己经有不少学者提出了对n a i v e 的d h t 网络中关键词连接的改 进方法。在文献f 1 8 1 中，d h t 网络事先存储了由字典里面单词组成的所有可能 的查询，这样就避免了在网络上做连接操作，但是这种方法需要很大的存储 空间和计算代价。在文献f 3 2 1 中，作者采用了b l o o mf i l t e r s ，缓存和i n c r e m e n t a l j o i n 的方法来减少连接操作的代价，取得了比较好的效果。在文献 2 5 中，作 者结合了很多现存的方法来进一步减少连接操作的代价，并指出即使结合所 有的方法，d h t 网络中的关键词搜索还是不能支持i n t e r n e t 规模的搜索。在文 献f 3 4 】中，作者提出了在s k i p n e t 上面用多层索引的方法使得关键词连接操作在多 层上并发进行，从而减少介绍了连接操作的执行时间，但是这种方法并没有本 质上减少带宽消耗，而且还增加了系统中的消息数目。在文献f 4 1 1 中，作者通 过实验实现并比较了在d h t 网络上进行关键词搜索的几种方法。实验得到的结 1 2 相关工作 果是，结合b l o o mf i l t e r ，缓存，预计算，查询日志挖掘和i n c r e m e n t a lj o i n 技术 并且当每个节点利用1 6 0 的额外预计算空间和2 5 6m b 的缓存的时候，d h t 网 络中关键词连接的通讯代价可以减d , n 原来的0 0 1 7 5 倍。 e s e a r c h 3 6 也是在d h t 网络上面进行关键词搜索的一种方法，它跟其他方 法不同的地方是不需要进行关键词的连接操作就可以检索文档。当发布文档 的时候，e s e a r c h 用信息检索的方法在每个文档里面选择一小部分重要的单词 发布到对应的节点，但是发布的信息则是整个文档的单词列表，而不是单词 的m e t a r l a t a 。通过这种发布机制，e s e a r c h 能够保证对于多个关键词的查询只需 在本地节点进行，不需要在网络里面进行连接操作。e s e a r e h 的缺点是它需要消 耗相对于传统方法6 8 倍的存储代价，并且查询的准确率随着用户需要返回的文 档数目的增长而迅速下降。 1 3 第三章 d h t 网络中信息发布和搜索技术研 究 3 1 引言 d h t 网络是结构化对等网络的一个重要代表，目前已经有很多文献研究了如 何在基于d h t 的对等网络中进行文档的发布和检索。我们已经在第二章的相关 工作中对现有的研究成果做了简单介绍。 现存的方法都是通过发布基于t e r m d o c u m e n t 的索引信息和在d h t 网络中进行 关键词的连接操作来实现的。当一个节点发布文档的时候，它把文档里面每个 单词在文档里面的m e t a d a t a 和对应文档的i d 发布到d h t 网络中对应的节点去。 当用户发起了个含有多个关键词的查询以后，含有这些关键词的文档列表以 及关键词在每个文档的m e t a d a t a 必须在网络中从一个节点传输到另外的节点， 来执行关键词的连接( j o i n ) 操作。当网络中存储了很多文档的时候，这种在网络 中传递文档列袭的方法势必会消耗很大的存储代价和网络带宽。图3 1 表示了传 统的d h t 网络中进行关键词搜索的方法。 p e e r s i n v e r t e dl a d e xo np e e r ，0 j - 溜 teterm-dogtllllmltin如 tftermid f m e t “口f 、 【t z l l 乜 r y 。 | t e r m d o t ；t l m e f l th f o t e r m d o c l df m e t a d a t a l h t jj 1 4