（计算机软件与理论专业论文）基于并行搜索簇网络的关键字排序搜索.pdf

基于并行搜索簇网络的关键字排序搜索 摘要 在p 2 p 网络环境中进行关键字排序搜索需要解决全局统计信息搜集的问题。 集中式的处理方法，要求网络中至少存在一个中心结点，进行统计信息搜集及排 序计算的工作。但是在p 2 p 这样一个分布式的环境中，期待着有中心结点的出 现有时并不合理，而且，即使存在中心结点，由于t 作任务的集中，这些结点上 的负载也会很重，限制了网络规模的可伸缩性。在本文中，我们采用的是一种分 布式的处理方法：基于并行搜索簇网络进行关键字排序查询。 1 通过将统计信息的收集和排序计算的工作分布到簇内的各个结点上进行并 行处理，我们降低了查询处理的响应时问，并将负载分摊到网络中的每个结 点上，从而充分利用了网络中的现有资源，改善了网络规模的可伸缩性。 2 我们并没有建立起一个关于网络中存在的所有关键字的全局索引，只是在接 收到查询请求的时候，才进行与此特定查询相关的全局统计信息收集和排序 计算，这大大降低了网络带宽和查询处理时间的消耗； 3 为了减少在网络中进行查询转送所消耗的带宽，我们将查询处理限制在一个 簇之内的范围，但是这样并不会遗漏位于其他簇内的相关文档信息，冈为我 们会对索引信息在网络中进行定程度地复制和散布： 4 我们考察了两种索引信息：结点层次的索引信息和文档层次的索引信息，前 者虽然在查询结果质量方面稍逊一筹，但可以大幅度地节约网络带宽以及存 储空间的消耗。 通过大量的实验，我们验证了在p 2 p 环境下，基于并行搜索簇网络的关键 字排序查询是一种有效的内容搜索方式，网络中的结点负载均衡，网络规模的可 伸缩性得到改善。 关键字：并行搜索簇网络关键字排序查询，t f i d f ，统计信息，排序计算 基于并行搜索簇网络的关键字排序搜索 a b s t r a c t t op e r f o r mr a n k e dk e y w o r ds e a r c hi np 2 pe n v i r o n m e n t ，t h ep r o b l e mo fg l o b a l a g g r e g a t ei n f o r m a t i o nc o l l e c t i o nn e e dt ob es o l v e d a c c o r d i n gt op r e v i o u ss o l u t i o n si n ac e n t r a lw a y , i ti sr e q u i r e dt h a ta tl e a s to n ec e n t r a lp e e re x i s t si nt h en e t w o r k , w h i c h w i l lc o l l e c ta g g r e g a t ei n f o r m a t i o nf r o ma l lt h ep e e r si nt h en e t w o r ka n dt h e nc a l c u l a t e t h eg l o b a lr a n k i n g h o w e v e r , i ti so f t e nu n r e a s o n a b l et oe x p e c ts u c hf lc e n t r a lp e e ri na d i s t r i b u t e de n v i r o n m e n tl i k ep 2 pn e t w o r k e v e ni ft h e r ei sac e n t r a lp e e r , s i n c ei th a s t od oa l lt h ej o b s ，i ti su s u a l l yh e a v i l yl o a d e d ，t h u sr e s t r i c t i n gt h es c a l a b i l i t yo ft h e w h o l en e t w o r k i nt h i sp a p e r , w ea d o p tad i s t r i b u t e dw a y ：1 0p e r f o r mr a n k e dk e y w o r d s e a r c ho v e rp a r a l l e ls e a r c hc l u s t e rn e t w o r k s 1 b yd i s t r i b u t i n gt h ec o l l e c t i o no fa g g r e g a t ei n f o r m a t i o na n dt h ec o m p u t a t i o no f r a n k i n go v e re a c hp e e rw i t h i nac l u s t e r , w ec a l ld e c r e a s et h eq u e r yr e s p o n s et i m e ， d i s t r i b u t et h el o a do v e rt h ew h o l en e t w o r k sm o r ee v e n l nt h u se x p l o i t i n gt h e e x i s t i n gr e s o u r c e si nt h en e t w o r k sf u l l ya n di m p r o v i n gt h es c a l a b i l i t yo fn e t w o r k s i z e 2 ，a c t u a l l yw eh a v en o tb u i l tag l o b a li n d e xf o re a c he x i s t i n gt e r mi nt h en e t w o r k i n s t e a d ，w ec o l l e c ta g g r e g a t ei n f o r m a t i o na n dc a l c u l a t er a n k i n go n l yi f w er e c e i v e aq u e r y , a n dd ot h a tw i t hr e s p e c tt ot h eg i v e nq u e r y , w h i c hc a ng r e a t l yr e d u c et h e c o s to f n e t w o r kb a n d w i d t hc o n s u m p t i o na n dq u e r yp r o c e s s i n gt i m e 3 。i no r d e rt os a v et h eb a n d w i d t hc o n s u m p t i o nd e d i c a t e df o rq u e r yf o r w a r d i n g ，w e r e s t r i c tt h eq u e r yp r o c e s s i n gw i t h i nac l u s t e r , i n s t e a do ft h ew h o l en e t w o r k h o w e v e r , t h ec o m p l e t e n e s so f q u e r yr e s u l t si sn o ta f f e c t e d ，s i n c ew ew i l lr e p l i c a t e l o c a l i n d i c e sa n dd i s t r i b u t et h e ms o m e w h e r ei nt h en e t w o r k 4 w eh a n d l ew i t ht w ok i n d so fi n d i c e s ：i n d i c e sa tp e e rl e v e la n di n d i c e sa t d o c u m e n tl e v e l t op e r f o r mr a n k e dk e y w o r ds e a r c hb a s e do nt h ef o r m e rk i n dw i l l r e s u l ti nal i t t l ew o r s ep r e c i s i o nf o rq u e r yr e s u l t s ，b u ta g r e a tr e d u c e i nt h e c o n s u n l p t i o no f n e t w o r kb a n d w i d t ha n ds t o r a g es p a c e t h r o u g h e x t e n s i v e e x p e r i m e n t s ，w ev a l i d a t e f o rc o n t e n ts e a r c hi np 2 p e n v i r o n m e n t ，r a n k e dk e y w o r ds e a r c hi np a r a l l e ls e a r c hc l u s t e rn e t w o r k si sa ne f f i c i e n t w a y , w i t he v e n l y - d i s t r i b u t e dl o a do v e re a c hp e e r , a n dt h ei m p r o v e ds c a l a b i l i t y k e y w o r d ：p a r a l l e l s e a r c hc l u s t e rn e t w o r k s ，r a n k e d k e y w o r ds e a r c h ，t f x l d f a g g r e g a t ei n f o r m a t i o n ，r a n k i n gc a l c u l a t i o n 2 基于井行搜索族网络的关键字排序搜索 1 1 背景介绍 第一章引言 近年来，p 2 p ( p e e r - t o p e e r ) 搜索网络作为一种可以在大量结点 例如连接到因 特网的p c 机) 之间分享资源的方式，越来越受到大家的欢迎了。同以往的客户机 服务器架构不同，在p 2 p 网络中，每个结点既能提供一定的本地资源在网络中共 享，也可以在其他结点提供的共享资源中搜索自己需要的内容，也就是说，一个网 络结点可以同时扮演客户机和服务器这两种角色。当参与p 2 p 网络的结点数量十 分庞大的时候，即使单个结点所能提供的资源比较有限，从整个网络的角度看，其 中的共享资源也会是非常丰富的。因此，p 2 p 是一种对现有资源充分利用的有效方 式，特别是在现有网络中缺乏价值昂贵、性能卓越的处理机的情况f 。 在网络中共享的资源可能包括数据、存储空间和计算能力等多种形式，但还是 以数据的共享为主。因此，在p 2 p 的分布式环境下，对于目标数据的有效搜索变 得极为重要。早期的p 2 p 系统如n a p s t e r 2 1 ，主要是用于分享多媒体文件，例如 m p 3 ，在这种应用环境下，只要输入歌曲名称中的几个关键字，就基本上可以确定 对应的文件，因此搜索只要基于文档的标题就足够了。之后出现的一些结构化p 2 p 网络系统，例如c a n 8 】和c h o r d 1 1 ，其共同特点是利用d h t ( d i s t r i b u t e dh a s h t a b l e ) 为数据分配唯一的对象标识符，并根据这个对象标识符决定数据在网络中的 存放位置，因此，在这些系统中，搜索是根据数据的对象标识符进行的。但在目前 的情况下，相较于其他种类的数据，文本数据仍然是我们获取信息的一个重要来 源，在p 2 p 的网络环境下，会有越来越多的共享文本文档出现，这将是一个必然 趋势。而且，在p 2 p 网络中每个结点都拥有一定程度的自主性的情况下，要求严 格控制数据的存放位置并不合理，因此，在文本文档在网络中的分布未知的条件 下，根据文档的内容进行搜索显得尤为重要。 基于关键字的文本内容搜索是信息检索领域中发展得已经比较成熟的技术。由 于在p 2 p 的网络环境下，共享文档数量众多，关键字查询所得到的查询结果数量 也往往十分巨大，因此有必要对查询结果按照与查询的相关性进行排序。 第一章引言 t f i d ff 9 】是经典的关键字排序搜索技术，它根据关键字出现在特定文档以 及全部文档中的频率判断该关键字的重要程度，而后根据特定文档包含的重要的查 询关键字的数量对文档进行排序。但是，排序过程所需的一些全局的统计信息，例 如全部文档的总数、特定关键字出现在全部文档中的频率，在p 2 p 网络环境中很 难搜集和维护，因为这些信息散布在整个网络中的所有结点上，而p 2 p 环境下的 结点，不但数目巨大，而且处于经常变动中( 结点的加入和退出、本地其享文档的 舔加和删除) 。 集中式的解决方法，要求网络中存在至少一个中心结点，负责全局统计信息的 收集和文档排序的计算，这对中心结点的性能( 如网络带宽、c p u 处理能力) 提出 了很高的要求。即便是由高性能的处理机担任中心结点，由于它要处理来自网络中 全部结点的汇总信息，而网络结点的数量十分庞大，很容易在性能上产生瓶颈，并 引起单点失败( s i n g l ep o i n to f f a i l u r e ) 的问题。可以说，中心结点的性能，限制了 p 2 p 网络规模的可伸缩性。 1 2 本文贡献 在本文中，我们寻求的是一种分布式的解决办法。通过选择一种特定的网络拓 扑结构，我们可以在之上进行有效的统计信息搜集和文档排序计算，并将负载分摊 到网络中的每个结点上从而充分利用了网络中的现有资源。这种特定的网络拓扑 结构就是由c o o p e r 等人 4 ，5 】提出的并行搜索簇网络。在这种拓扑结构下，网络 中的结点聚集得到若干结点簇：每个结点属于并且只属于一个结点簇；在一个簇内 部，结点之间是强连通的，簇内产生的查询会被传送到簇内的所有结点上进行处 理i 在簇与簇之间，网络连接只用来传送结点上共享文档的本地索引，从整体上来 看，一个簇所接受到的来自其他簇的索引信息，涵盖了位于其他结点簇的所有结 点，因此，即使查询处理限制在一个结点簇的内部，我们也可以搜索到整个网络中 的全部相关信息；这样的结点簇，我们称之为并行搜索簇。 既然在一个并行搜索簇内部就可以得到整个网络中全部结点上的索引信息 而每个簇内产生的查询都会得到簇内所有结点的处理，我们可以将与查询相关的统 计信息的搜索也作为一个查询，传送到簇内的每个结点上进行处理，而发出查询的 结点( 简称为“查询结点”) 就会得到汇总的全局统计信息；查询结点将全局的统计 信息再次传送到簇内的每个结点上，关于此查询的本地排序计算就可以在每个结点 基于并行搜索簇网络的关键字排粤搜索 上并行地进行，之后查询结点会得到汇总的全局排序结果；为了减少网络传输的代 价，簇之间传送的索引信息可以以结点为单位的，而非以单个文档为单位。因此全 局的排序结果可以是对结点的排序，而非文档排序，为了获得相关文档，查询结点 需要向全局结点排序中级别最高的k p 个结点( 即网络中与该查询最为相关的k p 个 结点) 发出查询，这k p 个结点将并行计算关于此查询的本地共享文档排序，最后查 询结点会得到与此查询最为相关的k d 个文档。 从上面的描述我们可以看到： 与集中式的处理方法不同，在网络中不存在一个中心结点负责收集全局的统 计信息以及进行排序计算，这个工作由簇内的所有结点共同承担，查询处理 的负载因此得到较为平均的分配，这降低了对网络节点性能的要求，改善了 网络规模的可伸缩性： 在网络中并没有实际建立起一个全局索引只是在接收到查询请求的时候， 才进行与此特定查询相关的全局统计信息收集和排序计算，这进一步降低了 网络传输 1 3 c p u 处理的负荷； 将查询处理限制在一个簇之内的范围，减少了在网络中进行查询转送消耗的 网络带宽，但是这样并不会遗漏位于其他簇内的相关文档： 无论是结点的排序计算，还是文档的排序计算，都是在多个结点上并行进行 的，这缩短了查询处理的响应时间。 1 3 本文结构 本文的正文结构如下：第二章将介绍一些相关工作；第三章介绍并行搜索簇 网络；第四章插述我们所提出的关键字搜索算法盼技术细节；第五章介绍实验情 况；最后，第六章是总结及对将来工作的展望。 墨王蒸堑堡室堡堕堑塑薹垦主篓生塑塞 第二章相关工作 本文的相关工作分为以下三个部分进行介绍：p 2 p 环境下的一般搜索形式已 有的在其他网络拓扑结构上进行关键字排序查询的工作，并行搜索簇网络简介。 2 1p 2 p 环境下的搜索 早期的p 2 p 系统，例如n a p s t e r1 2 】，g n u t e l l a 【1 】1 。主要是用于在用户之间分享 多媒体文件，例如m p 3 ，在这种应用环境下，只要输入歌曲名称中的几个关键 字，就基本上可以确定对应的文件，因此将搜索限制在文档标题( 以及一些关于文 档的附加信息) 的范围内已经足够。 之后出现的一些结构化p 2 p 网络系统，例如c a n 【8 】和c h o r d 【1 l 】，其共同特 点是利用d h t ( d i s t r i b u t e dh a s ht a b l e ) 为数据分配唯一的对象标识符，并根据这个 对象标识符决定数据在网络中的存放位置，因此，在这些系统中，只要根据数据的 对象标识符就可以快速有效地查找到目标数据。 但在目翦的情况下，相较于其他种类的数据，文本数据仍然是我们获取信息的 一个重要来源，在p 2 p 的网络环境下，会有越来越多的共享文本文档出现，这将 是一个必然趋势。而且，在p 2 p 网络中每个结点都拥有一定程度的自主性的情况 f ，要求严格控制数据的存放位置并不合理，因此，在文本文档在网络中的分布未 知的条件下。根据文档的内容进行搜索显得尤为重要。 基于文档内容的关键字搜索是信息检索领域中发展得已经比较成熟的技术。根 据共享文档中出现的关键字，我们可以建立一个从关键字到文档的索引，例如倒排 表，以便于对查询作出快速准确的回答。由于在p 2 p 的网络环境下，共享文档数 量众多，关键字查询所得到的查询结果数量也往往十分巨大，我们有必要对查询结 果按照与查询的相关性进行排序9 1 。 6 第二章相关工作 2 2 在其他网络拓扑结构上进行的关键字排序搜索 关键字排序搜索可以在不同的网络拓扑结构上进行。在底层的网络基础结构之 上，p 2 p 搜索网络形成了一个新的网络拓扑。在p 2 p 搜索网络中成为邻居的结点之 问，存在着在逻辑上持久稳固的网络连接。在不同的网络拓扑结构中，查询的路由 方式不同，索引信息的分布也会不同：索引可以仅仅本地存储在共享文档所在的结 点，索引也可以传送给周围的几个邻居结点1 0 ，1 3 ，甚至可以散布到整个网络环 境中【6 ，7 】。 在非结构化的p 2 p 网络中，例如g n u t e l l a 【l 】 结点可以任意选择它们的邻居 结点，而查询会被传播到网络中的任何地方，文档标题的索引信息只在本地存储。 c a n 【8 和c h o r d 【1 1 1 采用d h t 方法控制数据对象在网络中的存放位置，网络 中的每个节点都负责维护它的若干邻居的信息，以便根据数据对象的i d 进行有效 的查询路由；即使有新的结点加入网络，或者是现有的结点退出网络，邻居结点的 信息也可阻得到动态维护。 n a p s t e r 【2 】采用的是集中式的索引方法，在这个系统中，每个结点不仅把自己 的文档索引传送到一个中央结点存储下来，也把所有的查询传送给这个中心结点进 行处理。尽管这种p 2 p 查询网络易于实现，但却对中心结点的性能( 如网络带宽、 c p u 处理能力) 提出了很高的要求，容易引起性能上的瓶颈以及单点失败( s i n g l e p o i n to f f a i l u r e ) 的问题。可以说，中心结点的性能，限制了p 2 p 网络规模的可伸缩 性。 p l a n e t p 【7 】实现了非结构化的p 2 p 网络上的关键字排序查询。在这一系统中， 每个结点都建立一个本地共享文档的倒排表索引，并且通过流言方式( g o s s i p i n g ) 复 制到网络中的任何地方。因此，每个结点都拥有关于网络中所有结点的索引信息， 查询处理可以在任一结点上本地进行。至于具体的排序计算，p l a n e t p 提出了 t f x l p f 方法对结点按照与查询的相关性进行排序。实验证明，t f x l p f 方法的性能 与t f i d f 方法接近。但是，在整个网络中复制索引信息的代价很大。 超级结点网络上的关键字排序查询1 0 1 ，是在多个层次卜对文档进行摘要和索 引。在超级结点网络1 4 中，一些高性能的结点( 如网络带宽大、处理能力强) 担 任着超级结点的角色，而其他普通结点会把它们的文档索引和查询发送给这些超级 结点。超级结点之间的连接类似于g n u t e l l a 的非结构化网络拓扑结构。首先，每个 结点使用v s m ( v e c t o rs p a c em o d e l ) 和s v d ( s i n g u l a rv a l u ed e c o m p o s i t i o n ) 对本 基于并行搜索簇捌络的关键字排序搜索 地共享文档进行摘要，形成本地索引：然后，超级结点汇总它所管辖的所有结点的 摘要信息，形成结点群一级的索引，摄后，超级结点之间相互交换索引信息，从而 得到全局的索引信息。而查询处理的顺序与建立索引的顺序正好相反，超级结点首 先快速定位与查询相关的结点群，而后进一步定位在这些相关的结点群中与查询有 关的结点，而相关文档的查找则在这些相关结点本地进行。可以看到，与n a p s t e r 所采用的集中式索引方法类似，网络中超级结点的负载很重。 2 3 并行搜索簇网络 除此之外，还有一些其他的网络拓扑结构，比如我们在本文中选择的并行搜索 簇网络 4 ，可以作为关键字排序搜索的下层基础。 在这种拓扑结构下，网络中的结点聚集得到若干结点簇：每个结点属于并且只 属于一个结点簇；在一个簇内部，结点之间是强连通的，簇内产生的查询会被传送 到簇内的所有结点上进行处理：在簇与簇之间，网络连接只用来传送结点上共享文 档的本地索引，从整体上来看，一个簇所接受到的来自其他簇的索引信息，涵盖了 位于其他结点簇的所有结点，因此，即使查询处理限制在一个结点簇的内部，我们 也可以搜索到整个网络中的全部相关信息：这样的结点簇，我们称之为并行搜索 簇。 上述的非结构化p 2 p 网络、超级结点网络、以及并行搜索簇网络都可以用s i l ( s e a r c h i n d e xl i n k ) 模型【5 】来表示。我们将在第三章着重介绍s i l 模型，以及并行 搜索簇网络。 基于并行搜索簇网络的关键字排序搜索 第三章网络拓扑 在本章中，我们除了介绍s i l 模型之外，还要将非结构化p 2 p 网络、超级结点 网络和并行搜索簇网络用该模型表示出来。 3 1s i l 模型 在s i l ( s e a r c h i n d e xl i n k ) 模型 5 冲，网络连接被分为四类： n s l ( n o n f o r w a r d i n gs e a r c hl i n k ) ：从结点a 到结点b 的n s l 连接，使得结 点a 可以把查询转送到结点b ，结点b 根据本地的索引信息进行查询处理 并将查询结果返回给结点a 。 f s l ( f o r w a r d i n gs e a r c hl i n k ) ：从结点a 到结点b 的f s l 连接，使得结点a 可以把查询转送到结点b ，结点b 除了根据本地的索引信息进行查询处理并 将查询结果返回给结点a 之外，还会通过其他f s l 连接将查询发送出去。 n i l ( n o n f o r w a r d i n gi n d e xl i n k ) ：从结点a 到结点b 的n i l 连接，使得结点 a 可以把本地索引信息传送到结点b ，结点b 根据本地的索引信息以及结点 a 的索引信息进行查询处理，因此即使查询没有转送到结点a 进行处理， 查询结果中也可能包含结点a 上的内容。 f i l ( f o r w a r d i n g i n d e x l i n k ) ：从结点a 到结点b 的f i l 连接，使得结点a 可 以把本地索引信息传送到结点b ，结点b 可以进一步通过其他f i l 连接将结 点a 的索引信息发送出去，每个结点都根据本地的索引信息以及它所接受 到的其他结点的索引信息进行查询处理。 第三章网络拓扑 ( a ) 2 。 o _ 一j ? j _ j 0 。 ( c ) u n s t r u c t u r e dp 2 pn e t w o r k s u p e r p e e rn e t w o r k p a r a l l e ls e a r c hc l u s t e rn e t w o r k s u p e r - p e e r ( n o r m a l ) p e e r一f s l一n i l 图1 ：s i l 模型表示下的网络拓扑 3 2 非结构化p 2 p 网络 在非结构化的p 2 p 网络中，例如g n u t e l l a 【1 ，结点可以任意选择它们的邻居 结点，而查询会被传播到网络中的任何地方，索引信息只在本地存储。在s i l 模型 中，非结构化的p 2 p 网络可以用完全由f s l 构成的强连通图来表示，如图1 ( a ) 所 示。 3 3 超级结点网络 超级结点网络【1 4 中，一个超级结点负责维护它所管辖的普通结点的索引信 息，也负责处理来自这些普通结点的查询，超级结点之间是强连通的，可以用来转 发查询。用s 1 l 模型表示的超级结点网络如图l ( b ) 所示，网络中存在着从普通结 点到它所对应的超级结点的n i l 和f s l 连接，以及超级结点之间的f s l 连接。 r 、 一f ，二二卜，y_-0甲答万川_， 咛 一 ，l f l 0 ， 基于并行搜索簇网络的关键字捧序搜索 3 4 并行搜索簇网络 在并行搜索簇网络【4 中，网络结点聚集得到若干结点簇：每个结点属于并且 只属于一个结点簇；在一个簇内部，结点之间是强连通的，簇内产生的查询会被传 送到簇内的所有结点上进行处理：在簇与簇之间，网络连接只用来传送结点上共享 文档的本地索引，从整体上来看，一个簇所接受到的来自其他簇的索引信息，涵盖 了位于其他结点簇的所有结点，因此，即使查询处理限制在一个结点簇的内部，我 们也可以搜索到整个网络中的全部相关信息；这样的结点簇，我们称之为并行搜索 簇。在s i l 模型表示下，簇内结点以f s l 连接相连，簇间的网络连接是n i l 。图1 ( c ) 是一个并行搜索簇网络的例子，在此图中，从簇1 到簇2 、簇3 存在着n i l 连 接，当然簇2 和簇3 也有向外的n i l 连接，但在此图中为了清晰起见被省略了。从 整体上看，簇2 和簇3 都拥有簇1 内所有结点的索引信息。所以，即使查询处理只 在簇2 和簇3 内部进行，也可以搜索到位于簇l 内结点上的内容信息。簇l 、2 、3 内部的网络连接都是f s l 。 相较于超级结点网络，并行搜索簇网络充分利用了网络中的现有资源，将查询 处理的代价分摊到簇内的每个结点上，避免在整个网络中进行查询转发，节约了网 络传输的代价，降低了对网络节点性能的要求，网络规模的可伸缩性得到改善。但 并行搜索簇网络的缺点在于，结点必须将它们的索引信息发送到网络中其他的所有 簇中，如果索引的更新率很高，这会带来很重的网络传输负载。并行搜索簇网络最 适合应用的场景，是网络中结点的性能相差不大，并且搜索带来的负载远远大于索 引更新带来的负载，有理由相信，这在p 2 p 环境下是一种相当常见并且重要的情 况。 基于并行搜索簇网络的关键字排序搜索 第四章关键字排序搜索 在这一章中，我们首先介绍v s m 模型及t f x l d f 算法，然后形式化地描述我 们提出的关键字排序搜索方法所涉及的参数，之后给出该方法的实现过程，最后是 一个关于代价的简单分析。 4 。1v s m 模型和t f x l d f 算法 v s m ( v e c t o rs p a c em o d e l ) 9 1 模型可以用来表示文档内容。文档所包含的关键 字被赋予相应的权值( 例如出现频率) ，由关键字及相应权值组成的向量用来表示文 档内容。关键字查询也可以用相应的向量表示。v s m 模型中，计算关键字权重的 经典算法是t f i d f ，其中t f ( t e r mf r e q u e n c y ) 表示关键字出现在特定文档中的频 率，而i d f ( i n v e r s e d o c u m e n t f r e q u e n c y ) 表示关键字在其他文当中出现的频率，前 者考虑到，如果一个关键字反复出现在特定文档中，那么有可能它能够很好地描述 该文档的内容，是重要的关键字，后者则观察到，如果一个关键字频繁出现在多个 文档中，例如关键字t h e ，那么它对区分这些文档的帮助不大。一个关键字的 重要性由这两个因素共同决定。而文档与查询之间的相关性取决于两者的向量之间 的相似度，如两个向量的点积。 t f x i d f 算法的实现有多种方式，在本文中，我们采用w i t t e n 等人 1 2 】提出 的计算公式： wd ，= 1 + l o g ( 厂d ，) w 叫= i d f ，= l o g ( 1 + 一) ( 1 ) 其中，而，表示关键字t 在文档d 中出现的频率，表示文档集合中全部文档的 总数，表示包含关键字f 的文档数量。文档与查询之间的相关牲按照如下公式计 算： 己wd ，f w 口， 所m ( q ，d ) = 旦 r ( 2 ) 其中，吲表示文档d 所包含的关键字总数。 第四章关键字排序搜索 关键字排序算法依赖于倒排表索g l 的这一数据结车勾。给定一个文档集合，倒 排表索引记录了从关键字到文档的映射关系：一个关键字t 关联着它在其中出现的 一系列文档d ，以及在这些文档中被赋予的权值w n ，。此外，索引中还包含一些全 局的统计信息，如全部文档的总数、包含特定关键字t 的文档数量f ，用于计算特 定查询q 所包含的关键字的权值w 。之后，按照公式( 2 ) 计算出来的文档与查询 之问的相似度，我们可以对文档进行排序。 4 2 形式化描述 在p 2 p 这样的分布式环境下，除了由每个结点自身所维护的本地索引之外， 我们还需要搜集一些全局的统计信息，以便进行全局的关键字排序搜索。全局索引 的形式如下： g t e r m l i s t = ( g t e r m l ，g t e r m2 ，g t e r m 吖) g t e r m ，= ( g i ，g g ，g m 巧7 1 ，) ( 1 f m ) g z f l 巧7 1 ，= ( g f 1 ，g 只2 ，。，g f 品) ，。 i p l i s t = ( 置，p 2 ，户) g n u m l i s t = ( d 1 ，d 2 ，d ) 其中，慷示整个网络中出现的关键字总数，g _ 露莨示在以字母顺序排列下， 整个网络中出现的第i 个关键字，g g l 表示在整个网络中包含关键字g _ 乃的文档或 结点数量，表示网络中的结点总数，g 二厅( ， 9 表示关键字g 一矗在结点，上出 现的次数，整个网络中的结点按照它们的i p 地址排序，b 和d j ( ! d 分别表示结 向钧i p 地址和在结向上出现的关键字总数。 全局索引的建立以每个结点上的本地索引为基础： ，一t e r m l i s t ，= ( ，一t e r m ，l ，一t e r m 2 ，f t e r m j 。m ，) ，一t e r m 艰= ( ，一t m ，一g ，一i s t 建) ( 1 k m ，) l g l i s t j k 。q 一，球1 ，- 一，m 2 ，一一，m 。i 1 ( n d o c l i s tj = ( d ，i ，d 2 ，d j ，。，) ，一n u m l i s t = ( d 少d 妒，d ，) 基于并行搜索簇网络的关键字排序搜索 其中，w r m l i s t j 表示结向上的本地索引，哟表示在结向上出现的关键字总 数，t j k 表示在以字母顺序排列下，结点，上出现的第 个关键字，一瓠表示在结向 上包含关键字l 如的文档数量，n j 表示结点，上共享文档的总数，l 知( ，f ，吩) 表示 关键宁，t j , 在结点，上第r 个文档中出现的次数，结点上的文档按照文档名称的字母 顺序排列，a o d i s t j 表示结点，上的文档列表，彩和( 1 _ r s 彩分另“表示结赢，上文档r 的名称以及在文档r 中出现的关键字总数。 全局索引与本地索引之间的关系如下： ，。f ，一厶， 女，一f 肚一z u 一，f = 1 】s = 4 j 0 o t h e r w i s e g g ，= f r e q u e n c y 止( 5 ) 妒e q u e n c y 。= l 一；93 5 ，l o ，悃l 胩。= i s g e r | 本地索引的建立依赖于该结点上共享文档所对应的文档向量： 普：蠢_ c r 51 1 ：诅m b 兰2 l j j ! ：! r 七8 y w d r d 胛= ( w m )( ，s ) 、 其中，v 办表不结i 哥上文档r 所对腰明文档同量，矗表不结忘，上文档，中出现的 关键字数量。h ( j ss - - - - - - 幼表示在以字母顺序排列下，结向上文档r 中出现的第s 个关键字，面铷( j ! 链+ 仂表示关键字在结点，上文档，中出现的次数。 本地索引和文档向量之间的关系如下： l 靠= t o o 丑, 幽w j r 。s 三业 ，一g 旷l f r e q r “p 厅钞” ( 7 ) i s h t ， 脚明钞，= 锯孙篇 第四章关键字排序搜索 4 ，3 算法实现 我们首先来看一一r 索引建立的过程。索引的建立最早是从文档向量的建立开始 的。经过预处理，去掉停用词( s t o pw o r d ) 以及进行词干提取( s t e m m i n g ) 之后，文档 向量就比较容易得到了。我们用列表来实现，r e r 州f 蛳和，。在文档向量的台_tflist，k 并过程中，出现一个新的关键字就会对应一个新的，被插入到，中，_ t e r m # m r m l 曲o 其中，g 以及zt f l 嘲i 所有分量都初始化为0 。如果出现的是已经存在的关键字， ，斑和，鼽相应增加。最后，一个本地索引就可以在结, 电jl - 建立起来了。 既然在这篇文章中，关键字排序搜索是在并行搜索簇网络的基础上进行的， 正如我们在第3 章所看到的，除了自身的本地索引之外，一个结点上还会存储若干 来自其他簇的结点的本地索引信息，因此，根据存在于一个簇之内的索引信息，我 们就可以建立起全局的索引。 4 3 1 文档层次的索引信息 假设在簇之间传递的文档信息是整个本地索引的全部信息，我们则称之为文档 层次的索引信息，因为索引中包含了每个关键字在每个特定文档中出现的次数。 全局索引信息的收集是被新进的查询所激活的。发出查询的结点( 我们称之 为查询结点) ，将查询q 一( k e y w o r d + , k e y w o r d 2 , 勋j m o r d q ) 连同自己的i p 地址发送到 网络中，其中华表示该查询中包含的关键字的数目。在并行搜索簇网络中，这样一 个查询会被簇内的所有结点接收到，但是不会被其他簇的结点接收到，因此查询就 被限制在一个簇之内的范围。收到查询以后，结点p 统计它本地的统计信息 d o cn u m p j 】i l ( f r e q 咖f r e q 2 p ，户e q 曲： d o c h u mp = n ， e q 。= z g 且 ( ，g ) ( 8 ) 其中，卵表示结点，的本地索引信息存储在结点p 的索引库p 中，d o c _ n u m p 表) v 那些本地索引信息存储在结 勋上的结点的共享文档总数，加表示在上述这些结 点上包含关键字托y w o 磁t 的文档数目。得到这些本地统计信息之后，结点p 将它们 发送给查询结点。根据簇内各个结点传来的本地统计信息，查询结点可以得到关于 查询q 的全局统计信息： 基于并行搜索藏网络的关键字捧宁搜索 d 0 c 一u m = d o c l q l l m ，= ， p e c f eje g g ，= f r e q 。， 其中，p e c 表示结点p 属于当前的簇c 。回想我们曾介绍过参数表示整个网络 中出现的结点总数，n j 表示结点，上共享文档的数日，因此d o c u 燎示整个网络 中共享文档的总数。g - g ，表示在整个网络中包含关键字g 乃的文档数目。因为查 询q 中只包含了g 个关键字，所以gg 。也只针对这q 个关键字进行了计算，而不是针 对整个网络中出现的全部朋个关键字进行计算，这大大节省了计算的代价。全局的 统计信息会在整个簇内传播，因此每个结点都可以针对查询q 按照相似度对文档进 行排序，文档一( 即结点，上的第价文档) 与查询q 2 _ 间的相似度计算，根据公式( 1 ) 和f 2 ) 改写如下： s i m r ，口5 1 + l o g ( 一厶) 】l o g ( 1 + d o c n u m g g ，) 盟生飞一( 1 0 ) d ， 。 其中，g - 乃= “m 。排序的过程在簇内的各个结点上并行执行。最后，本地的 排序结果被返回给查询结点，并被查询结点合并成为关于查询q 的全局排序。 如果用户所要求的共享文档数目k ，远远小于网络中存在的共享文档总数， 我们可以限制簇内结点返回给查询结点的文档排序结果只是与查询q 最为相关的 个文档，而不是与查询q 相关的所有文档列表，这样可以大大节省网络带宽的消 耗。 4 3 2 结点层次的索引信息 假设簇之间传送的索引信息由结蔚上的g 二乃，g 乃，马和岛( 窿心m 3 毛 ，“= g 以) 组成，我们则称之为结点层次的索引信息。采用这种方式，用于簇问索 引信息传输的网络带宽将大大减少，特别是在索引更新率高的时候。 在这种情况下，由簇内结点p 收集的本地统计信息包括怖索引信息在结 点p 卜存储的结点数目，以及： 咖g 妒21 ( 1 “q ) ( 1 1 ) ，p g t i = k e y w o r d 。 其中。r e q ，表示关键字纫w d 嘲，在那些索引信息存储在结点p 上的结点出现的 次数。因此，关于查询q 的全局统计信息为： 第四章关键字排序搜索 n = n ， p c g g 。； p e c k e y wo r d 。= g ( 1 2 ) 其中，慷示整个网络中的结点总数。同样地，g - - g ，只针对查询q 所包含的g 个 关键字进行计算，而不是针对网络中存在所有关键字。全局的统计信息会被传送到 簇内的所有结点上，因此这些结点可以针对查询q 按照相似度对结点进行排序，结 向和查询q 之间的相似度计算，根据公式( 1 ) 和( 2 ) 改写如下： 1 + l o g ( g 一气) 1 0 9 ( 】+ g g ，) j z 朋j , q2 。2 i 一( 1 3 ) u j 其中，毋表示结点，上出现的关键字总数。 这种情况下，查询结点得到的全局排序结果是关于结点的排序。要准确定位 与查询q 相关的文档，查询结点需要直接与排序最高的b 个结点建立连接、发送查 询，而这拓个结点会在本地针对查询q 对自己的共享文档进行排序。排序是基于文 档办与查询q 之间的相似度计算： 【1 + l o g ( 一) x l o g ( 1 十行，一g 一) a i m ) r ，o2 。了一( 1 4 ) u f 因为关于文档的索引信息并没有在结点之间进行交换以获得全局的统计信息， 所以由这些结点返回给查询结点的本地排序结果包含的是本地排序最高的b 个文 档，查询结点会对这些文档进行台并，得到全局排序最高的幻个文档返回给用户。 基于并行搜索簇网络的关键字排序搜索 5 1 网络拓扑 第五章系统实现及实验 网络规模( 见表1 ) 参照c o o p e r 等人f 4 的实验设置，其中网络中的结点数目为 1 0 0 。首先，我们希望通过实验得到与c o o p e r 等人相似的结论，所以参数设置最好 能够保持一致。其次，其他用真实数据集在不同网络拓扑上做的关键宇排序搜索实 验，结点数目为：3 0 【1 0 、1 0 0 、4 0 0 【6 】，而在模拟实验中，网络结点规模可以达 到1 0 ，0 0 0 s o 。 p a r a m e t e r d e s c r i v t i o n b a s ev a l u e n u m b e ro f p e e r s1 0 0 p 口a v e r a g eo u t d e g r e e sp e rp e e rf o rp l o d 5 p m a x i m u mo u t - d e g r e e sp e rd e e rf o rp