（计算机应用技术专业论文）基于最优搜索理论的信息检索系统的研究.pdf

摘要 摘要 随着互联网的普及以及现在多媒体技术的日新月异，对多媒体信息尤其视频信 息的检索己成为信息检索领域的一个研究热点。国内外就视频检索方面的研究早 已开始并取得了一些成就，有效的解决了视频检索在互联网上的应用。然而随着 互联网上多媒体信息每日信息量成指数倍的增加，传统的视频检索系统还是存在 一些局限性，例如搜索效率太低、搜索准确性不高、缺乏实时性等问题，如何有 效地进行视频检索成为当前的研究热点之。 为了提高视频检索系统的效率，研究人员提出了一些新的思路。从视频搜索网 络中资源的组织方式角度考虑是本文的基本思想，论文中所提出的具有c l u s t e r 特 性搜索资源的无结构对等网络结构模型是从网络结构组织的角度考虑，然后应用 最优搜索策略，将搜索网络中存在的搜索主体看成对等个体，同时综合考虑搜索 主体中存储的待搜索资源所具有的c l u s t e r 特性，透明化搜索网络为一个虚拟网络， 该模型的参与者包括：搜索主体，待搜索资源，需求资源，q u e r y m e s s a g e ，c l u s t e r 特性。最终本文应用最优搜索理论来提高采用以上模型的视频检索系统的效率， 搜索引擎系统中通过归类和重组多媒体信息，并按照模型存储到虚拟网络中。 论文首先考虑了最优搜索理论和现今视频信息检索领域的结合点，然后提出四 种可选的搜索网络结构组织模型，通过进行仿真实验和数据对比，最后找到视频 检索系统适用的网络结构模型，并给出应用在这种模型中的最优搜索策略，从而 进一步建立视频检索系统的最优搜索模型。使用m i c r o s o f t 公司的n e tf r 锄e w o r k 2 o 框架和s u a ls n l d i 0 2 0 0 5 作为开发平台，并采用成熟的网络系统开发技术 r e m o t i n g 、交互技术a j a x 实现基于最优搜索理论的视频检索研究的成果系统，经 过实验验证并采用最优搜索时间和最优搜索代价两个参数来衡量系统的效率后得 出结论：基于最优搜索理论的视频检索系统能够一定程度上克服传统视频检索系 统的局限性、并提高搜索性能。 对于下一步的研究方向，本文讨论了具有c l u s t e r 特性的无结构对等网络中不 同的搜索策略，希望能够从密集查找和随机游走两种搜索策略继续研究和完善视 频检索系统。 关键词：最优搜索理论，c 1 u s t e r 特性，搜索主体，q u 郫m e s s a g e a b s t r a c t a sm ep o p u l 撕t yo ft h e1 1 1 t e m e ta n df 瓠td e v e l o p m e l l to fm u l t i m e d i a t e c h n o l o g y ， r e s e a r c ho nm u l t i m e d i ai n f o n n a t i o nr e t r i e v a le s p e c i a l l yo nv i d e oi n f o m l a t i o nr e t r i e v a l h a sb e c o m eo n eo ft h eh o tr e s e a r c hp o i n t si ni n f o m a t i o nr e t r i e v a l6 e l d r e s e a r c h e r sa l l o v e rm ew o d dh a v ea c h i e v e ds o m es u c c e s s 伽s t 印sa n da l s oa p p l yv i d e oi n f o m a t i o n r e l 慨a lo ni n t e n l e t s u c c e s s 血1 1 y h o w e v e r ， a sm ed a i l ye x p o n e l l t i a li n c r e 嬲eo f m u l t i m e d l am f o m a t i o no nh l t 翎：1 e t ，t r a d i t i o n a l d e 0s e a r c h e l l 百n es t i l lh a ss e v e 脚 1 1 m i t a t i o n ss u c ha sl o ws e a r c he 伍c i e i l c y ，l o ws e 卸c ha c c u r a c ya 1 1 ds o o n t h e r e f o r e h o wt 0m a k ee f f e c t i v e “d e 0i n f o n n a t i o nr c t r i e v a lh a sb e c o m e0 n e o fn l eh o t t e s tp o i n t s o fc l 盯e n t l yr e s e a r c h r e s e a r c h e r sh a v ep u tf o 刑a r ds o m en e wt h i n 】( i n g i no r d e ft 0 i m p r o v et h e e f f i c i e n c yo fv i d e 0i n f o n n a t i o nr e t r i e v a ls y s t e m i ti st l l eb a s i cm i n k i n gm e t h o dm a t t l l i l 埘n g 舶mm ep e r s p e c t i v eo fo 唱a n j z i n gf i l e si nm ev i d e 0i n f b n n a t i o nr e t r i e v a l n 咖o r k ，t h eu 1 1 s n u c n i r e dp e * t o - p e e rn 咖o r kw i t hc l u s t e 秆e dd 锄a n d sn e 铆d r km o d e l r 锄l n d e di no u rp a p c rm i l l l ( sm es e a r c ha u t h o r si ns e a r c hn e 咖r ka se q u a lp e e r sb v c o n s l d e n n gt 鼻o mn e 魄o r ks 细c n h e do r g a 芏l i z a t i o n ，m e a f l w h i l ei tt h i n kt h ec l u s t e r p r o p e n i e so 硒1 e s 砌c ha r es t o 础i ns e a r c ha u t l l o r ss oa st 0 仃a i l s p a r e n ts e a r c hw e b 内r av i r t u a ln e t 、硼r k - t 1 1 em o d e l sp a i t i c i p a n t si n c l u d e ：s e a r c ha u m o r s ，n e e d sr e s o u r c e s q u 唧m e s s a g e ，c l u s t e rp r o p 鳅i e s u l t i m a t e l y ，w eu s e o p t i m a is e a r c ht h e 0 巧t 0i m p r 0 v e n l ee 施c i e n c yo fv i d e or e t r i e v a ls y s t 啪w h i c hu s i n gt 量l ea b o v et h e o r e t i c a l m o d e l ，a tm e s a m et l m e ，as e a r c he 1 1 晷n ec a ns t o r ef i l e si n t o 、，i r t u a ln e m o r ki na c c o r d a n c ew i t hm e m o d e lo f r m a ls t o r a g et ot l en e 帆o r kb yc l a s s i f i c a t i o na 1 1 dr e o r g a l l i z a t i o n s i l lt h j sd l s s e r t a t 主o n ，r e s e a r c h 钌s 行r s tc 0 n s i d e r e dt h ep o i n tw h e r et o c o m b i n e o p t i m a ls e a r c ht l l e o 巧a i l dm e 缸e i do fv i d e oi n f o n i l a t i o nr e t r i e v a l ，t h e np u tf o n a r df o u r o p t l o n a in e t w o f ko r g a n i z a t i o nm o d e lo fs e a r c hn e 觚o r ka 1 1 d l a s tf o u n dt h em o s t a p p r o p n a t eo n eo fv i d e oh f o n n a t i o nr e t r i e v a ls y s t 锄缸。u 曲s i m u l a t i o na n dd a t a c o m p a n s o n a l s or e s e a r c h e r sg a v et l l eo p t i m a ls e a r c hs t r a t e g ) ，o fa p p l y i n gm em o d e l t o s e a r c hn e t w o r k ，w h i c hw i l l 觚h e re s t a b l i s hm eo p t i m a ls e a r c hm o d e lo fm ev i d e o m t - o m a t i o nr e t 】n e v a ls y s t e m h lt h i s d i s s e r t a t i o n ，r e s e a r c h e r sd e v e l o p e dm ev i d e o a b s t r a c t i n f b 衄a t i o nr e t r i e v a ls y s t e mb a s e do no p t i m a ls e a r c ht l l e o wb yu s i n g n e tf r 锄e w o r k 2 oa n dv i s u a ls t u d i o2 0 0 5o fm i c r o s o rc o 叩o r a t i o na so u rd e v e l o p m e n tp l a t f o m i ，a s w e l la sr e m o t i n gt e c h n o l o g yw h i c hi st h ea d v a l l c e dn e 抑o r ks y s t e md e v e l o p m e n t t ec _ h i l o l o g ya i l d a j a xt e c h n o l o g y w 1 1 i c hi sc o m m u n i c a t i o n t e e h n 0 1 0 9 y a r e r e x p e r i m e n t a lv e r i f i c a t i o n ， r e s e a r e h e r sc o n c l u d e dt h eb e l o wc o n c l u s i o n t 1 1 r o u 曲 m e a u s u r i n gm ee m c i e n c yo ft h es y s t e mu s i n go p t i m a ls e a r c ht i m ea i l do p t i m a ls e a r c h c o s t ：t oac e r t a i ne x t e n t ，t h ev i d e 0i n f 0 h n a t i o nr e t r i e v a ls y s t 锄b a s e do no p t i m a ls e a r c h t h e o 拶c a no v e r c o m em e 仃a d i t i o n a lv i d e oi n f o m a t i o nr e t r i e v a ls y s t e m sd e f i c i c n c i e s a n di m p r o v es e a r c hp e r f 0 n n a n c e a sm en e x ts t e pmm er e s e a r c hd i r e c t i o n ，s i n c em i sp a p e rh a sd i s c u s s e dd i f - f e r e m s e a r c hs 躐e 百e sa p i p l i e di nt h eu n s t n l c t u r e dp e e r - t 0 i p e e rn e t 啪r kw i t hc l u s t e r e d d 锄a n d sn e 帆o r km o d e la sw e na st h e i rd i f l f e r e n te m c i e n c y w ed oh o p et oi m p r o v et h e v i d e or e 仃i e v a ls y s t e me 佑c i e i l c ym m u 曲m u c h 如r t h e rs t u d yo nm et w os e a r c h s 觚t e 西e so fn o o ds e a r c ha n dr a n d o mw a l k k e y w o r d s ：o p t i m a ls e a r c hm e o 巧，c l u s t e rp r o p e n i e s ，s e a r c ha u t h o r ，q u e 叫m e s s a g e 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得电子科技大学或其它教育机构的学位或证书而使用过的材料。 与我同工作的同志对本研究所做的任何贡献均已在论文中作了明 确的说明并表示谢意。 签名：翌丛日期：瓞年 o ，口， o ，x = 1 ，2 ，6 ( x ，五) = o ，a = o 公式( 3 4 ) 探测函数以一种概率的方式对搜索资源分配的有效性进行衡量，实际应用中 则需要根据搜索问题的具体情况而定。目标总的探测概率表示为： 尸【厂 = d ( z ) 6 ( 五( x ) ) 公式( 3 5 ) 电子科技大学硕士学位论文 其中厂是资源分配方案，它给出了搜索空间中每个单元的资源分配量，也可 称之为搜索策略。因为总探测概率与是否在该位置搜索有关，而和每一项是否出 现无关。 总代价函数为： c 门= c 似厂( z ) ) 一 公式( 3 6 ) 其中c ( x ，厂( x ) ) 是分配厂( x ) 资源到x 处的代价函数，为讨论方便，论文中设 c ( x ，( x ) ) = 名。 3 4 拉格朗日乘数法 拉格朗同乘数法l a 伊a n g em u l t i p l i e r 是一种基本的搜索理论用于寻找最优搜索 计划【1o 】【1 1 】【1 2 】。 用最优搜索理论对所研究的问题建立了数学模型之后，接下来就需要求解这 个数学模型，从而得到关于资源分配的最优搜索策略。 拉格朗日乘数法可以用来解决任意实值目标函数在任意实数集上的带约束条 件的最大值问题。约束条件由定义在同一个实数集上的有限个实值函数的值给出。 拉格朗日乘数法求解最优化问题较简单、直观，很多情况下都适用，特别适合于 解决如何将有限资源分配到一组独立的单元中去的问题。此外，在应用拉格朗日 乘数法求解带约束条件的最优化问题时不会受到函数的可微性要求的限制。所以 在这里是研究中选用的种优化方法。 按照前面的定义： 尸 厂】= d ( z ) 6 ( x ，厂( z ) ) 公式( 3 7 ) 要得到最大探测概率p 【门且满足约束条件： y 丑k ， 一 f = l 公式( 3 8 ) 其中k 是资源上限。通常解这样的极值问题是困难的。相对来讲，解无约束 条件的极值问题却比较容易。拉格朗日乘数法把约束条件和需要求极值的对象放 第三章最优搜索理论介绍 在一个式子中考虑，将带约束条件的极值问题转化成普通的求极值问题。 构造拉格朗日函数，如下： ，( f ，r ，五) = p ( f ) 6 ( f ，彳) 一祝，l f ，五 0 ，f 0 公式( 3 9 ) 其中f 叫做拉格朗日乘子，它是一个参数。该函数叫做逐点拉格朗日函数 ( p o i n 似i s el a 铲a n g e 矗m c t i o n 1 3 】 1 4 】【1 5 】。根据s t o n e 的研究，对于一个参数旯的可容 许资源配置厂( f ) 是最优配置的充分条件是，对于某个f o ，厂( f ) 满足： ，( f ，死厂( f ) ) = m a x p ( f ，r ，力) l 旯 o ) ，f = 1 ，2 ， 公式( 3 一l o ) 对z 求导： 掣：p ( f ) 矽( z ，五) 吒 d 九 i、。 一。 通过求解p ( f ) 6 t ( f ，五) 一r = 0 可得最优搜索方案如下： 丑：f ( f ) ：1 n 地 并且五必须满足搜索总成本开销约束条件： 争a ：争l n 盟k 以= l n 掣k 公式( 3 1 1 ) 公式( 3 1 2 ) 公式( 3 一1 3 ) 令乃= k ，可以求得对应的f 值。 本章详细介绍了最优搜索理论的基本知识，包括构成该理论的3 个基本要素， 还确定了在研究中根据实际情况将采用的具体函数形式，要应用最优搜索理论到 实际信息检索领域需要建立最优数学模型，这些将在系统的实现章节具体给出。 1 9 电子科技大学硕士学位论文 第四章信息检索系统适用的网络结构模型 4 1 可选的网络模型 将搜索范围内具有搜索资源的搜索主体集合看成一个搜索网络的话，搜索策略 制定就需要考虑此搜索网络的逻辑结构组织，换句话说就是搜索网络的拓扑结构 组织，在这里提出以下几种可选的搜索网络模型： 4 1 1 星形网络拓扑 星形网络拓扑结构的提出思路来源于物理网络中局域网的网络结构组织，局 域网中这种网络拓扑结构是由中央节点和通过点到点的链路与中心站相连。特点 是很容易在网络中增加新的站点，数据的安全性和优先级容易控制【1 8 】【1 9 】【2 0 】【2 l 】，易 实现网络监控，但中心节点的故障会引起整个网络瘫痪，链路由中央节点到各个 站点组成。 通过上面的描述可见，星形拓扑结构具有以下优点：控制简单、故障诊断和隔 离容易，方便服务。而星形拓扑结构的缺点如下：电缆长度和安装工作量可观、 中央节点的负担较重，形成瓶颈、各站点的分布处理能力较低。 结合论文研究中涉及到的搜索网络( 虚拟网络) 中来说，拥有一部分搜索资源 的搜索主体和一个中央节点( 中转结点) 可以组成星形搜索网络，每个搜索主体 都和这个中央节点之间保持连接，搜索引擎直接和这个中央结点进行交互和通信， 询问搜索网络中是否具有需求资源，中央结点将这个询问消息发送给与之相连的 其他结点( 搜索主体) ，如果搜索主体没有，则返回一个消息给中央结点，中央结 点再根据搜索主体的反馈决定是否继续向下面剩余的搜索主体发送询问消息，这 是文中提出的这种搜索网路拓扑结构的基本工作模式和组织关系。 具体的逻辑组织图可以参看图4 1 2 0 前叫章信息榆常系统适川的嘲络结构模c 】_ 圆 倒曙 斟4l 星形网络拓扑结构模胤理h 图中f 【! 设有3 个搜索丰体，这二个搜索丰体中各存储有搜索资源的部分， 1 i j 户通过网络向搜索系统发j _ 带搜索关键字的搜索，然后w e b 搜索系统将直接发 出询问消息给中央结点，中央结点冉将带有搜索关键字的咖问消息发送给搜索t 体，并等待姻复，再次定下一步的措施。 在这种网络结构模型中，因为它结构简啦，弃易实现，而且增加搜亲主体非 常方便，新加入的搜索主体不但可以增加搜索资源数、扩人搜索网络，同时它也 增加了搜索到需求资源的概率。但是由于每次搜索指令的发出都需要搜索引擎和 中央结点之间变百，各个搜索t 体相对被隐减到了后端，切搜索指令均通过中 央结点发出所以潜在的威胁就是r 中央结点m 现异常，搽个搜索恻跚都将稚 痪。 412 总线网络拓扑 基于总线拓扑结构的原理，结合论文中涉及到的项目这早还提出的另外 一种网络拓扑结构：总线网络拓扑结构。县有总线刚络拓扑结构的搜索州络中所 有的搜索土体将共享条搜索数据通道。总线型网络实现起来简单方便，需要的 仪是搜索主体需要共享的通道( 缓冲池) 。总线网络拓扑结构中搜索主体将被搜索 引擎以轮询的方式通过数据通道询问是否具有需求资源，搜索 体将币定时收到 8 俪 电子科技大学硕士学位论文 询问消息，如果某个搜索主体拥有需求资源的话，它将发出信号告知搜索引擎， 搜索引擎会做出反应停止向搜索数据通道频繁发送出带有关键字的询问消息 ( q u 叼椰e s s a g e ) 。在这种网络拓扑结构中，和搜索引擎交互的有搜索数据通道和 各个搜索主体，搜索数据通道更多的是承担一种媒介的作用，它传输询问消息给 各个搜索主体，并将获得的反馈消息传递给搜索引擎，在这里它完成的是各个搜 索主体和搜索引擎之间的交互。 搜索过程中对于需求资源的询问消息不像上面的星形网络拓扑结构还有一个 中间结点进行转发和控制，在这种拓扑中不再具有分布式的实时性了，因为每当 搜索系统发出询问消息后，要搜索主体通过数据通道接收到询问消息后才能够再 做出反应，之后搜索系统又才能够根据数据通道中接收到的询问消息做出下一步 操作，在这样的网络拓扑结构中搜索效率会有一定影响。关于总线网络拓扑结构 搜索网络的实际工作原理和机制，参照图4 2 。 从图4 2 中可以看到，在用户、搜索引擎和搜索主体集合之间与上面的星形网 络结构不同的是多了一个数据通道机制，用户通过网络向数据通道发送带关键字 的询问消息后，该询问消息将被传达到每一个搜索主体处，或者说每一个搜索主 体将不定时收到询问消息，因为搜索引擎采用的是轮询的方式来发送询问消息给 数据通道，而因为网络原因和搜索主体自身探测数据通道的频率不同，搜索主体 收到询问消息的时间会不同，但是一旦它们收到询问消息后将对比自身所存储的 搜索资源，做出反应：一旦发现自己具有需求资源，他们将发送信号在数据通道 中，告知搜索引擎该搜索主体具有需求的资源，这样此次搜索工作成功结束，搜 索引擎也不再发送带搜索关键字的询问消息直到又一次搜索工作开启。 总线网路拓扑结构中某个搜索主体的故障一般不会影响整个搜索网络。但数 据通道的故障会导致搜索网络瘫痪，总线网络拓扑结构的搜索网络安全性低，监 控比较困难，增加新搜索主体也不如星型网络拓扑容易。 辩网幸信包捡索系统适川的网络纠栅模型 建 整 甚 鹾 。曼”f “i 。绸一n 削42 总线h 络拓扑结曲模掣原理i 斟 41 3 基于最优搜索理论的灾难恢复搜索网络拓扑 以上提出的可选搜索网络结构组织借鉴丁物理网络的结构组织方式，如粜将 搜索系统中儿是具有需求资源的所有自治体看成一个馕，那么将搜索过程中从 一个自治体中没有搜索到需求资源这类事件( e v e n t ) 看成次灾难( d l s a s t e r ) 的 话川，则灾难恢复就是指如何从余下的自治体中选出可能具有需求资源的过 程田。那么根据中提出的灾难恢复模型，经过模型元索的转换，将灾难恢 复晶优模犁应片j 在信息榆索系统中，则可以提出基于最优搜索理论的灾难恢复搜 索模型： ( 1 ) 符号说明 符号说明是为了简明扼要地给出灾难恢复系统中用到的特殊符号以及它们如 何和信息检索系统中虚拟的搜索网络巾的元素结合起来： 口：灾难恢复的搜索代价预算限额，即足指当从当前艘索j 二体处搜索到需求资 & 币 芸旦蚧 。_ i ? ? 毋妙一莎一 电子科技大学硕+ 学位论文 源的概率为0 时，制定策略挑选出下一个自治体进行需求资源搜索需要耗费的搜 索代价 么：搜索系统中所包含的自治体的集合 s 。：业务应用( 自治体) 口的重要程度 f ：需要保护的设施( 搜索询问过程) 厂的集合，可以是软硬件设备等，它对 业务应用具有重要价值。通常信息系统包含多个口，每个业务应用需要依靠多个设 施厂才能够实现其功能。另一方面，一个设施厂可能会对多个业务应用口提供服务。 可见口和厂之间通常是多对多关系。这里的设施，对应信息检索系统中的一次搜索 询问过程，即使针对某一搜索主体就是否存储需求资源的搜索询问操作。 d 后：设施厂的失效会影响口正常运行的可能性 w ，：设施厂相对所有业务应用的重要性，吩= 5 。j 丘。 口月 尺。：对于有些消耗性资源，它们只需要付一次费用，只能被使用一次，这些资 源构成集合尺。在这里，论文假定搜索系统中，所有的自治体都是消耗性资源。 因为对于一次搜索询问过程( 设施厂) 来说，一个搜索主体是否存在需求资源经 过一次询问就可以了，之后便会对除此搜索主体之外的其余剩余搜索主体进行询 问，所以对于信息检索系统来说这个网络模型中的所有搜索主体集合构成r 。 尺。：还有一些资源，只需要付一次购买费用，之后可以反复被使用，这些资源 构成尺。 心：某些资源需要在每次使用时交付租用费用，这类资源构成集合心。在本论 文中，信息搜索系统暂时未考虑此类资源。灾难恢复系统中确实存在这样的资源， 但是就本次研究工作中所涉及到的搜索网络而言为方便对比网络模型的性能，先 假设系统中不涉及到有尺。和民这两类资源 r ：灾难恢复需要使用的所有资源的集合，尺= r 。u 尺。u r 。经过前面的分析 第四章信息检索系统适用的网络结构模型 显然在搜索网络中r = r 。 p ：所有子灾难恢复计划( s u bd i s a s t e rr e c o v e 巧p l a i l s ) s d r p 构成的集合 弓：可以保护恢复设施厂的s d r p 构成的集合a 这里的保护设施厂可以映射到 搜索网络中针对某次搜索询问过程是否有效，即得到该搜索主体是否具有需求资 源结果所耗费的时间代价 p ：需要使用资源，的s d r p 构成的集合 0 ：当子灾难恢复计划p 能够提供对设施厂的保护恢复能力时，取值为1 ，否 则取值为0 m ，：对子灾难恢复计划p 能力的度量，m ，= 谢 l f 以p ：当需要子灾难恢复计划p 时，取值为1 ，否则取值为o g ，：资源，的数量 g ：子灾难恢复计划p 需要的资源r 的数量 c ，：资源，的单价。如果r ru 尺。，则c ，指一次性所付的费用。如果，尺。， 则c ，指相应的租金或薪水。显然本次讨论集中在c ，指一次性所付的费用 e ，：当选中资源r 时，取值为l ，否则为o ( 2 ) 目标函数 以p 朋p ( 3 ) 约束条件 ，l p y ， p p r 1 ， j 口e 岛 v ，1 ，= 1 ，2 ，3 ， 公式( 4 2 ) v 1 f 尼 公式( 4 3 ) ，| p g p ，一p ，譬，o ， v ，l 蜀 公式( 4 4 ) p e 只 脓( 刀，g ) 一巳吼o ，v 厂ru r 公式( 4 5 ) p e p r 电子科技入学硕士学位论文 e ，c ，+ 甩， 巳c ， b r u 只埘 p 6 j 口r e r “ 使公式4 1 具有最大值的s d r p 构成的集合就是最优的s d i 冲集合。 此模型的更细节分析具体可以参考【3 ，下面简要说明一下此类模型的具体实 施过程，这也是实际应用模型在信息检索系统中需要花较多精力注意的地方。 在研究被保护信息系统和灾难恢复系统的基础上，可以通过以下步骤使用这 个模型实现对d r p 【3 2 】【3 3 】的建立和评估分析。 ( 1 ) 搜索系统中所有重要应用，或者说搜索系统中存储有待选资源的各个搜索 主体。根据每个应用的重要程度赋以其相应权值，根据每个搜索主体上所具有的 待选资源数然后按照某种加权算法来赋给搜索主体不同的权值，构建应用向量 ( s 小s 。：，j 拼) 。向量中元素记录应用的权值，元素的下标代表系统中不同的应 用。 ( 2 ) 对所需资源进行标识和分类，构建3 个资源数量向量( r 。，尺。，r 。，) ， ( 足”r 。：，r 。，) 和( r 乜，又如，兄如，) 分别记录系统中3 种不同类型的资源数量。 构建资源代价向量( r ，r o ：，r ，尺卅i ，r 。：，r 。，r 啊，尺 ：，r b ，) 记录资源的单价， 这里搜索网络中所需资源的标识和分类应该非常简单。 ( 3 ) 评估搜索系统中需要被保护的所有设施【3 4 1 3 5 】( 搜索询问过程) 以及设施对 应用的影响( 搜索询问过程在不同搜索主体上执行的效率) 。通过这一步骤，构建 设旌矩阵，矩阵的行下标代表不同设旋，也即是不同的搜索询问过程，列下标代 表不同应用，也即是搜索询问过程在不同搜索主体上执行的效率，矩阵的元素记 录某个设施对某一应用产生影响的可能性： 办h a 圆。 d f 她 ； 九。： 屯。： a p 1 ； ，通过设施矩 阵可以计算出设施权值向量h ，叶j ，) ，该向量记录每个设施对所有应用总的 影响程度。 ( 4 ) 深入研究所有s d r p 并构建s d i 冲设施矩阵，矩阵的行下标代表不同 s d i 冲，列下标代表不同设施，矩阵的元素值为l 或o ，分别代表相应的s d i 冲是 2 6 勺 奶 q 屯呶屯； 第四章信息检索系统适用的网络结构模型 否能够保护相应设施： l p i z 以 z n 石 ： z 九，2 z p 2 z 几 ： ，类似地可以构建s d r p 资源矩阵， 矩阵的元素取值代表s d i 冲需要占用的相应资源的数目： 以t ，2 g p 2 r 2 g j 口3 r 2 ： ( 5 ) 借助于s d i 冲资源矩阵，分析系统并构建s d i u 冲突矩阵，矩阵的行下标 和列下标都代表不同应用，矩阵的元素为1 或0 ，分别代表不同应用之间是否会产 生冲突： ( 6 ) 基于这个数学模型和以上步骤，就可以设计开发软件工具或借助于一些优 秀的软件( 例如c p l e x ) ，设计开发辅助工具，辅助决策者进行灾难恢复决策，当 然对于本项研究最重要的是，研究工作可以基于这样一个模型来设计信息检索系 统，使之在新的搜索网络组织结构下具备更高的检索系统性能。 此模型应用广泛，尤其在信息系统中，由于系统的应用日益严重依赖于信息 技术，信息系统失效会对应用产生致命影响，所以灾难恢复的重要性也越来越突 出。本文的“灾难 以及超出了自然灾害的范畴，必须重申，对于信息检索系统 而言，灾难恢复更是指的搜索过程中对于一次自治体上面对于特定需求资源的搜 索以失败告终时，应该如何从余下的自治体资源中挑选下一个搜索目标，多媒体 搜索系统中，如果信息失效将使得整个搜索系统瘫痪，所以在此提出这种模型一 可以一定程度提高检索系统的性能，二也是为了能够有效的避免信息失效带来的 对搜索系统的损坏。以上仅是对此模型原理和模型原型中元素如何应用到信息检 索系统的简要介绍，对于模型的具体实施以及实施后的测试此处不详细说明，论 文后面将给出测试和对比结果。 以上提出的这种子灾难恢复模型，由于其应用了最优搜索理论，建立了数学 模型，来决定下一个进行需求资源询问的搜索主体，所以此模型在信息检索系统 中具有一定实用性，故而这里将其列入几种可选模型之中，以便对比和挑选。 。kk； 吩 巧 ； 3 3 3 既见a ； 电子科技大学硕七学位论文 4 1 4 具有聚类性资源的无结构对等网络拓扑 和以上提出的三种网络结构模型不同，具有聚类性资源的无结构对等网络结 构模型将各个搜索主体看成对等个体，而不是整体与个体的组织方式。 无结构对等网络中的基本元素是搜索主体，每一个搜索主体本身存储有一定 数量的搜索资源和其邻居主体( n e i 曲b o r ) 【6 】【3 6 】【3 7 】【3 8 1 的地址，搜索主体和它们各自的 邻居之间可以互相询问是否存储有需求的搜索资源，通过发送q u e r y m e s s a g e ( 询问 消息) 的方式。当搜索主体本身没有自己需求的资源时，可以快速的向邻居主体发 送q r l l e r y m e s s a g e ，如果邻居主体也没有被搜索的资源，q u e 圳m e s s a g e 会从邻居主 体处再次转发，转发的对象是随机选择的邻居但不能包括q u e r y m e s s a g e 的来源搜 索主体，以上过程一直持续直到找到需求的资源。 新进的搜索主体会带入额外的资源，从而帮助一个搜索主体存储的资源能够 被那些需要这些资源的搜索主体发现。因此在一个对等的网络中找到自己需要的 资源就成为一个严峻的研究课题。保持一个对每一个搜索主体提供资源的中央集 成的索引是一种解决办法，但是这种解决办法无疑进一步加重这种课题和单个搜 索主体失败的可能性。相反，一种更直接的方法来找到自己需要的资源就是让有 资源需求的搜索主体向其它搜索主体询问，以此来找到那个拥有需求资源的搜索 主体。因为一个结点实际上并不能保持所有其他搜索主体的位置或者地址 ( a d d r e s s ) ，故而一种覆盖性结构的网络应运而生，在这样的覆盖性网络中，每一个 结点保留有一些其他搜索主体的地址( 这些搜索主体被成为结点的邻居n e i 曲b o r s ) ， 而结点通过这些邻居就可以找到其他剩余的搜索主体了，进一步就可以找到结点 需求的那些资源，具体原理可以参照图4 3 ： 图4 3 是具有聚类性资源的无结构对等网络结构模型的原理图 2 8 第四章信息检索系统适川的网络结构模型 ! ；：! ；竺t * 幽4 3 具有累类盹资源的尤结构对等嘲结结# j 模型的原理h 从同4 3 中可咀看出，搜索网络中假定存在n 个搜索丰体，它们之叫地位对等， 可以可_ 相湖m ，当擅索辛体4 从搜索系统处接收到搜索系统的带关键7 检索指令 时，它首先和星形网络拓扑结构咀驶总线恻路拓扑结构一样在t 体自身所存储的 待选资源进行对比，如果存在需求资源则返叫信息结束此次搜索：如果不存在需 求资源，由于网络模型中的搜索主体存储的信息除了待选资源外还有对其邻居节 点( 搜索主体) 信息及其上面所存储的资源的部分记录，所以下一次搜索将从搜索主 体4 的邻居( 搜索主体l 和搜索主体3 ) 中选择个搜索主体进行再次搜索，这 里的选择有几种方式，可以随机选择，电可以根据一定的算法来进行选择，肖然 需要的就是耗费一些时叫来计算出叫能具有需求资源的搜索主体。如果这次搜索 还是不能搜索剑需求资源，则继续从搜索土体l 和搜索主体3 各自的邻居继续搜 索，这旱将不会对搜素主体4 进行搜索了。由于搜索主体之间可以相互询问足否 存在需求资源，这样的自发1 _ i = 搜索询问远比接收到一个搜索指令刭执行一次搜索 询问的方式大大提高了效牢。由于搜索主体存储得有邻居结点的信息，所以在挑 选进行下一次搜索的邻居结点时，检索系统是可以指定一定策略的，这样的话找 到需求资源的范围将更加缩小，需求的搜索时川代价也就越小。 举例中的搜索网络结构相刘实际应川叶 的较简单，实际应用中搜索土体4 的 邻居可能不j 2 个般足3 个以上( 例如搜索主体3 的邻居就不l 2 个：搜索 ，0 电子科技大学硕士学位论文 主体2 、搜索主体4 、搜索主体5 搜索主体n 都是搜索主体3 的邻居) ，按照上面 所描述的搜索策略循环下去，如同一棵二叉树越到叶子结点同级的结点数越多， 在这里就是指对需求资源的搜索路径越多，找到需求资源的概率越大、效率也越 高。 搜索主体随机从邻居列表中选择对象来转发q r l l e r y m e s s a g e ，若搜索网络中待 搜索资源在各个搜索主体中的存储方式毫无规律可循，则找到搜索资源时的搜索 时间和搜索代价都将是不稳定的。 进一步研究中假定无结构的对等网络是典型的用随机图作为模型驱动( 因为 每个搜索主体的邻居都是被随机选择的) 。已提供的仿真【4 0 】【4 1 1 可以得出结论：对于 搜索时间而言它可以作为需求资源复制品数量的一个功能，对于测量了的 g n c t e l l a 【5 l 跟踪拓扑和超级端( s u p e rp e e rt o p 0 1 0 9 y ) 拓扑( 每一个超级搜索主体有 很多叶子搜索主体( 1 e a f p e e r s ) 连接到超级搜索主体，并且超级搜索主体它们自己是 连接在一个e r d o s r e n y i 离散图拓扑结构中) 。 提出的这种覆盖拓扑结构模型能够被认为是一个具有从概率g 到基于利益的 快捷键的连接的e r d o s r e n y i 离散图，通过增加这些快捷键来构造具有i n t r a c l u s t e r 连接概率p 的结点的聚类性( p 留) 。一些相关的解决方案是【4 0 】【4 2 1 ，它们使用了 一个中央集成的服务器和一些超级端搜索主体在一个基于超级端搜索主体的网络 中，这些解决方案各自的找到具有相似利益的搜索主体，即寻找同样聚类性的搜 索主体。 除了前述提到的搜索机制，使用边界危险( e d g e 嘶t i c a l i t y ) 【9 】【4 3 】 删的混合型搜索 机制( h y b r i ds e a r c hm e c h a n i s m s ) 也能提供在这些拓扑结构中有效的搜索。基于过去 查询反应的直接查询搜索方法也能平衡资源普遍性尽管它们在搜索网络中的覆盖 并没有展示出聚类性。在【9 】【4 5 】中提到的建议使用向导规则( g u i d e r u l e s ) 来导向搜索找 到那些具有相似利益的搜索主体，这些搜索主体被他们作为相似利益记录下来来 分离无结构覆盖拓扑结构，从而得到不同的利益的共同体( d i 毓tc o m m u n i t i e so f i n t e r s t ) 。最后，尽管【2 2 】【4 6 】中提到的建议并没有提及到聚类性，但是当搜索资源普 遍性展示出聚类时，他们的解决方案也能够工作正常，因为有限的密集搜索 ( 1 i m i t e d - h o pn o o d s ) 同样能够发现本地聚类池( 1 0 c a lc l u s t e r ) 中的需求资源，另外 奇缺的需求资源( 例如那些在非本地聚类堆中的资源) 也有可能被发现通过一种 基于d h t 的机制( d h t b a s e d m e c h a l l i s m ) ，例如( 通过一种结构化的网络) 。必须 指出，确实还存在有许多其它的解决方案在杠杆聚类中在搜索资源的概率( 例如 第四章信息检索系统适刚的网络结构模型 因为空间限制研究中不能提及的工作在语义的覆盖【2 4 】【4 j 7 1 ) 。此处同样强调拓扑模型 拥有小规模的特征，论文中的搜索问题并没有映射来找到一个特殊的地址已知的 结点，这种情况需要在接下来的工作中在小规模网络中得继续处理f 2 0 1 。例如已经 构建起来的解决方案如【2 2 1 和能够得到【2 0 】中提出的构造网络使用搜索的d h t 抽 象。 d h t 抽象提供网络中一对一的从搜索资源到搜索主体之间的映射，从而找到 一个需求资源就能够通过翻译( 仃a j l s l a t e ) 而找到负责那个需求资源的搜索主体。 反过来，研究的工作假设多重的搜索主体可能拥有需求的资源( 正如已经被研究 了的放置系统中那些具有普遍性的搜索资源( p o p l l l a rf i l e 【1 4 1 【2 2 】) ，从而研究的搜索 不是为找到一个特殊的搜索主体( 这些搜索主体是拥有那些需求资源的) ，而是为 了寻找到任何拥有需求资源的一个搜索主体。实际上，研究工作的一个贡献就是 提出的可解析的关系，这种关系就是指研究所能够在搜索性能和需求资源的复制 品数量之间建立可解析的关系。然而【2 2 】提出的关于搜索性能的表达式作为复制品 数量的一个功能指标，他们的性能规则( p e 怕肌a i l c em e t r i c ) 是不同的。像其它的 有限点密集搜索h o p 1 i m i t e df l o o d i n gs e a r c h ( 离散搜索【2 9 】【3 l 】【3 6 】【3 7 】) 方案一样，他 们致力在最大允许的点数条件下( w i t l l i nt h em a x i m 啪n l 】m b e ro f h o p sa l l o w e d ) ，找 到匹配需求资源成功的概率和找到的不同需求资源搜索主体的数量。当然还有其 他可能的语法( 例如在一个给定的允许查询消息条数的限度下，找到的区域结点 的数量) ，但是找到目标的搜索时间和搜索代价却是更直接的性能度量。参考文件 吲和【2 5 】讨论了这些语法规定的搜索性能和在假设需求资源副本是统一分布的前提 下期望需求资源副本数量( 它假设所有的搜索主体都有相似的利益) 以及在限制 搜索主体结点的存储空间条件下的最优搜索性能之间的关系。 允许一个搜索主体的邻居被随机选择的对等网络在g n e t e