信息系统安全第6章.ppt

第六章 并行与分布式信息检索,信息存储与检索,本章目录,第一节 引言 第二节 并行信息检索 第三节 分布式信息检索方法 第四节 异构数据库检索,信息存储与检索,第一节 引言,在因特网大容量的信息检索中，传统的顺序技术会遇到检索速度下降的困难，而并行信息检索能够突破顺序检索的局限，大大加快检索的处理速度。因此，并行检索技术是提高信息检索系统的响应时间的一种有效途径。,信息存储与检索,第一节 引言,集中式检索系统有着很多的局限性：其一，网络信息量呈指数增长，集中式的检索方法不能适应信息急剧增长的需要；其二，虽然目前的搜索引擎都在努力的增加对网络信息的覆盖率，但要想覆盖整个网络上的信息在目前几乎是不可能的；最后，检索系统之间通常没有分工协作，各自独立搜索和处理信息，造成了大量的重复工作和严重的带宽浪费，有时甚至能造成网络阻塞。为了适应网络规模的日益扩大，有必要采用分布式处理技术解决网络中大量信息的检索问题。,信息存储与检索,第二节 并行信息检索,6.2.3 并行检索技术,3,3,6.2.4 并行检索中的索引文档处理,4,信息存储与检索,6.2.1 并行信息检索原理,（一）多个查询之间的并行处理 利用MIMD结构对多个查询的处理并行化，即每个处理器处理不同的查询，每个查询的处理之间相互独立，最多只对共享内存内的部分代码或者公有数据实行共享。这种方法也称为任务级的并行检索，它可以同时处理多个查询请求，从而提高检索的吞吐量。,信息存储与检索,6.2.1 并行信息检索原理,（二）单个查询内部的并行处理 即对单个查询的计算量进行分割，分成多个子任务，并分配到多个处理器上的搜索进程上去执行。这种检索也称为进程级并行检索。 将单个查询分成多个子任务的方法通常有两种：一种称为数据集分割，它是事先将数据集分割成多个子集合，用同一查询式分别查询多个子集合数据，然后将每个子集合上的结果合并成最终结果；另一种称为查询项分割，它是将查询分解成多个子查询，对每个子查询分别查询数据集，得到部分结果，并将部分结果合并成最终结果。,信息存储与检索,6.2.2 并行检索的体系结构,并行体系结构利用指令流和数据流的多倍性将计算机系统分为四类：SISD（单指令流单数据流）、SIMD（单指令流多数据流）、MISD（多指令流单数据流）和MIMD（多指令流多数据流）。SISD对应于传统的顺序处理体系结构, MISD十分少见。并行机器实际上只有两类：SIMD和MIMD。 SIMD结构是用同一指令并行操作不同的数据，因而是一种并行数据计算。 MIMD结构比SIMD复杂，其中处理器之间是独立的，对不同的数据执行不同的指令。MIMD是目前并行引擎所使用的主要结构。,信息存储与检索,6.2.3 并行检索技术,（一）并行检索策略 并行技术分为数据并行和功能并行（控制并行）。 数据级并行依赖于并行处理机，特点是重复设置许多个同样的处理单元，按照一定的方式相互连接，在统一的控制部件作用下，各自对分配来的数据并行地完成同一指令所规定的操作。 功能并行主要表现于多个任务或多个程序段之间，执行时可能存在着数据交往或控制依赖，因而解决起来较为复杂。但是随着并行技术的进一步发展，程序的控制并行间题将得到逐步解决。,信息存储与检索,6.2.3 并行检索技术,（二）并行检索软件技术 软件中的并行性主要是指程序的相关性和网络互连。 程序的相关性分为数据相关、控制相关和资源相关：数据相关说明的是语句之间的有序关系，控制相关指的是语句执行次序在运行前不能确定的情况，资源相关与并行事件利用整数部件、浮点部件、寄存器和存储区等共享资源时发生的冲突有关。 网络互连使用静态或动态拓扑结构网络。静态网络由点点直接相连而成，这种方式在程序执行过程中不会改变；动态网络可动态地改变结构，使之与用户程序中的通信要求匹配。,信息存储与检索,6.2.3 并行检索技术,（三）并行检索硬件技术 硬件技术方面主要从处理机、存储器和流水线三个方面来实现并行。 处理机系列包括CISC、RISC、超标量、VLIW、超流水线、向量以及符号处理机。 存储设备按容量和存取时间从低到高可分为寄存器、高速缓存、主存储器、磁盘设备和磁带机五个层次 流水线技术主要有指令流水线技术和运算流水线技术两种。,信息存储与检索,6.2.4 并行检索中的索引文档处理,（一）倒排表索引结构 检索系统通常采用倒排表（inverted file）索引结构，可直接从关键词映射到所在文档。,信息存储与检索,6.2.4 并行检索中的索引文档处理,（二）基于倒排表的分割处理 使用倒排表进行数据集分割有两种实现方法：物理倒排表分割方法和逻辑倒排表分割方法。这两者的数据集都在物理上分成多个子集合。 物理倒排表分割和逻辑倒排表分割的不同之处在于，前者不仅将数据集分割，而且将倒排索引表也同时进行分割，每个数据子集拥有自己独立的索引倒排结构。对于逻辑倒排表分割，倒排索引表物理上并不进行分割，而是增加一个处理机分配表，整张倒排索引表则被多个处理器共享使用。,信息存储与检索,6.2.4 并行检索中的索引文档处理,（三）SIMD机器上的倒排检索 SIMD机器也称阵列处理机，是由大量相同的互连的PE（处理单元）对分配来的数据并行执行同一指令所规定的操作。由主文档建立倒排索引可利用CU（控制部件）执行建库程序而完成。 对提问编辑与变换后形成的检索指令表，因其中某些广义检索指令基本上属于向量类指令，故需“播送”给各个PE，由它们并行地执行该指令规定的操作，而对其中的标量指令则由CU自己执行。,信息存储与检索,6.2.4 并行检索中的索引文档处理,（四）MIMD机器上的倒排检索 MIMD机器也即多处理机系统，它既可以是P台处理机共享一个主存的紧耦合多处理机，也可以是不共享同一主存的松耦合多处理机，能够实现作业、任务、指令、数组各级全面并行。在此硬件环境下，倒排索引及主文档可以分割存放，如倒排索引分放在内存各部分，主文档分放在并行辅存中，以便在检索时由各台处理机同时查找数据。,信息存储与检索,6.2.4 并行检索中的索引文档处理,（五）并行顺排检索 假若由p台处理机构成多处理机系统，处理由n个提问构成的批量提问检索，则相应有两种处理方案。 一、先将p个提问依次读入p台处理机，各自变换为提问展开表，得到前p个提问的检索结果后，接着读入p+1 2p个提问，直至所有提问处理完毕。 二、将n个提问同时读入每一台处理机中，p台处理机各自将每个提问展开，再将与其有逻辑联系的每篇文献编制成检索标识表，经重复变换和比较，每台处理机获得部分检索结果，最后将p组结果组合起来。,信息存储与检索,6.3.3 分布式信息检索模式,3,3,6.3.4 分布式检索中的数据集选择,4,第三节 分布式信息检索方法,信息存储与检索,6.3.1 分布式信息检索原理,分布式信息检索主要是指在分布式的环境中，利用分布式计算和移动代理等技术从大量的、异构的信息资源中检索出对用户有用的信息的过程。这里的分布式环境指的是信息资源在物理上分布于各地。这些分布式的信息资源在逻辑上是一个整体，从而构成一个分布式检索系统。但是，不同的信息资源具有不同的数据库结构，即分布式的信息资源具有异构性的特点。,信息存储与检索,6.3.2 分布式检索处理技术,由于不同的信息资源具有不同的数据库结构，因此在分布式环境下对于异构数据库的检索和访问并不简单。解决分布式信息检索的技术很多，如用于分布式数据库设计与实现的分布式对象组件模型（DCOM）和公共对象请求代理构架（CORBA），用于解决分布式环境中数据库之间异构问题的Z39.50协议、P2P网络结构技术等。而代理技术同样也可实现分布式信息的检索。,信息存储与检索,6.3.3 分布式信息检索模式,（一）基于元搜索引擎的分布式信息检索 元搜索引擎被称为搜索引擎的搜索引擎，它自己并不收集网站或网页信息，通常也没有自己的资源库和Robot。当用户查询一个关键词时，它把用户的查询请求转换成其他搜索引擎能够接受的命令格式，并行地访问多个搜索引擎来查询这个关键词，然后将返回的结果进行合并、排序等处理后，作为自己的结果返回给用户。,信息存储与检索,6.3.3 分布式信息检索模式,（二）基于Z39.50的分布式信息检索 根据ANSI/NISO Z39.50-1995（ISO 23950）的定义，该协议是计算机系统之间相互联系的一系列标准，它独立于任何特定类型的信息或特定类型的数据库系统。 Z39.50作为一个分布式环境下计算机系统之间进行通信的标准协议， 实现了异构机型、异种操作平台的异质数据源之间的相互操作，大大降低了异种数据库之间查询的复杂程度。,信息存储与检索,6.3.3 分布式信息检索模式,（三）基于XML的分布式信息检索 基于XML的分布式信息检索的基本思路是：每个对外提供数据检索服务的信息组织，可根据所属行业和数据的性质，选定某个已成为标准或被共同遵守的DTD作为与外界进行数据交换的格式，然后针对自身数据库的特点编制检索程序，检索出的记录按选定的DTD生成XML文档，并以XMLHTTP协议格式返回给用户。,信息存储与检索,6.3.3 分布式信息检索模式,（四）基于Web服务的分布式信息检索 Web服务（Web service）是一种可独立的、模块化的Web应用，它允许在Web站点上放置可编程的元素，能进行基于Web的分布式计算和处理。 位于服务器端的Web服务具有从数据库中检索数据的功能，同时还具有自描述功能，能够向用户提供调用参数、返回参数、端口地址等接口信息，方便用户调用。因此，可以利用Web服务来实现分布式信息检索。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（一）朴素法 朴素法（Nave Approaches）是一种简单的数据集选择方法，它不用判断成员搜索引擎对检索的有用性和有效性，直接将用户的查询请求发送给所有采用的成员搜索引擎进行检索。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（二）粗略法 粗略法(Rough Approaches)是一种提供每一个成员搜索引擎描述信息的数据集选择方法。在这类方法中，每一个搜索引擎的描述信息通常是以固定格式人工添加的。当用户提出一个查询式时，系统会将查询式与每个成员搜索引擎的描述信息进行匹配运算，并决定该搜索引擎的相关度。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（三）定性的方法 这类方法有的采用很粗略的信息来代表每个数据集的内容，数据集描述信息相对来说比较容易获取，更新容易而且占用很少存储空间，文档中单元词的频次信息计算也非常简单。不过过于简短的信息描述很难充分全面地反映数据集的内容，会遗漏潜在有用的数据集。 有的采用详细信息来描述数据集代表，涉及到在此数据集里每个文件中出现的每个术语。如果处理得当使用这种方法可探测到每个潜在有用的文件。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（四）定量的方法 定量方法评价数据集与查询之间的相似程度要更加具体和明确，可以为用户提供更多的有用信息。 该方法衡量成员搜索引擎数据集有用性的标准是： （1）成员搜索引擎数据集中对于每个查询的潜在有用文档数量。 （2）一个成员搜索引擎数据集中与给定查询最为相似的文档的全局相似度。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（五）基于学习的方法 这种方法根据以往的查询经验来预测数据集对于新查询的有用程度。 静态学习方法使用训练查询，每个成员搜索引擎关于训练查询的检索经验可以在使用前得到。 动态学习方法使用真正的用户查询，检索经验可以被逐步积累并持续更新。 混合学习方法是静态学习方法和动态学习方法相结合的方法。它通过训练查询得到初始经验，通过真实查询不断更新知识。,信息存储与检索,6.3.4 分布式检索中的数据集选择,（六）数据集选择方法的比较 准确性。朴素法没有任何计算，其准确性自然最差。粗略法的准确性有一定的提高，但由于描述信息比较简略，因此没有定性法准确。虽然定量法提供的数据对用户具有极大的参考价值，但还无法准确评估其准确性。 可扩展性。朴素法具有最高的可扩展性，因为它不保存任何成员搜索引擎的描述信息；粗略法由于为每个搜索引擎生成描述信息非常少，且与搜索引擎的规模没有关系，也具有很好的可扩展性。而后面几种更严格的选择方法对一个搜索引擎描述信息的大小直接与该搜索引擎中不同单元词的个数有关。,信息存储与检索,6.3.4 分布式检索中的数据集选择,可维护性。朴素法不需要收集和维护任何描述信息，而粗略法由于描述信息是由手工添加的，与搜索引擎中的个别文档无关，因此它们几乎不需要维护工作。定性法和定量法都需要建立和维护一些成员搜索引擎的描述信息，其可维护性完全取决于所需描述信息的多少。基于学习的方法，既不用计算初始数据集描述信息，也不用为搜索引擎更新而修改描述信息，只是在检索的过程中修改相应的描述信息，因此也具有较好的可维护性。,信息存储与检索,第四节 异构数据库检索,6.4.3 异构数据库跨库检索技术,3,3,6.4.4 异构数据集成,4,信息存储与检索,6.4.1 异构数据库的特点,（一）异构性。异构性主要体现在计算机体系结构、操作系统、DMBS本身、语义等方面。 （二）分布性。异构数据库系统的各个异构数据库分布在不同的位置，系统通过网络建立其之间的连接。系统的数据保存在各个异构数据库之中，这些数据可以以各种不相同的方式保存，没有严格的逻辑要求。 （三）独立性。包括数据的逻辑独立性和物理独立性。 （四）自制性。体现在拥有对自身系统内各种资源的使用权利，同时拥有与其它系统的交互权利。,信息存储与检索