第六章 并行与分布式信息检索 本章目录第一节 引言 第二节 并行信息检索 第三节 分布式信息检索方法 第四节 异构数据库检索2第一节 引言v并行信息检索主要依赖计算机并行处理技术。并行 处理是指把计算机任务划分为成更小的子任务，然 后多个处理器处理同一个任务的不同子任务，各处 理器采用并行工作方式。 v在因特网大容量的信息检索中，传统的顺序技术会 遇到检索速度下降的困难，而并行信息检索能够突 破顺序检索的局限，大大加快检索的处理速度。因 此，并行检索技术是提高信息检索系统的响应时间 的一种有效途径。3第一节 引言v集中式检索系统有着很多的局限性：其一，网络信 息量呈指数增长，集中式的检索方法不能适应信息 急剧增长的需要；其二，虽然目前的搜索引擎都在 努力的增加对网络信息的覆盖率，但要想覆盖整个 网络上的信息在目前几乎是不可能的；最后，检索 系统之间通常没有分工协作，各自独立搜索和处理 信息，造成了大量的重复工作和严重的带宽浪费， 有时甚至能造成网络阻塞。为了适应网络规模的日 益扩大，有必要采用分布式处理技术解决网络中大 量信息的检索问题。 4第二节 并行信息检索6.2.1 并行信息检索原理16.2.2 并行检索的体系结构 26.2.3 并行检索技术 336.2.4 并行检索中的索引文档处理456.2.1 并行信息检索原理（一）多个查询之间的并行处理v利用MIMD结构对多个查询的处理并行化，即每个 处理器处理不同的查询，每个查询的处理之间相互 独立，最多只对共享内存内的部分代码或者公有数 据实行共享。这种方法也称为任务级的并行检索， 它可以同时处理多个查询请求，从而提高检索的吞 吐量。66.2.1 并行信息检索原理（二）单个查询内部的并行处理 v即对单个查询的计算量进行分割，分成多个子任务 ，并分配到多个处理器上的搜索进程上去执行。这 种检索也称为进程级并行检索。 v将单个查询分成多个子任务的方法通常有两种：一 种称为数据集分割，它是事先将数据集分割成多个 子集合，用同一查询式分别查询多个子集合数据， 然后将每个子集合上的结果合并成最终结果；另一 种称为查询项分割，它是将查询分解成多个子查询 ，对每个子查询分别查询数据集，得到部分结果， 并将部分结果合并成最终结果。 76.2.2 并行检索的体系结构v并行体系结构利用指令流和数据流的多倍性将计算 机系统分为四类：SISD（单指令流单数据流）、 SIMD（单指令流多数据流）、MISD（多指令流 单数据流）和MIMD（多指令流多数据流）。 SISD对应于传统的顺序处理体系结构, MISD十分 少见。并行机器实际上只有两类：SIMD和MIMD 。86.2.2 并行检索的体系结构vSIMD结构是用同一指令并行操作不同的数据，因 而是一种并行数据计算。SIMD结构算法既可以建 立在标识档结构之上，也可以建立在倒排档结构之 上。它的指令需要传递给结构中的n个处理器。使 用这种结构的系统通常需要拥有大量的并行计算机 ，而这些计算机上都有相对简单的处理器，控制所 有同步处理操作的控制单元。处理器之间可能共享 存储器，也可能每个处理器都有自己的本地存储器 。 96.2.2 并行检索的体系结构vMIMD结构比SIMD复杂，其中处理器之间是独立 的，对不同的数据执行不同的指令。MIMD是目前 并行引擎所使用的主要结构。该结构通常还包括共 享的存储器或者一个通信网络。MIMD系统是对各 自的数据项完成独立的操作功能。 vMIMD并行体系结构主要由多个具有自己的控制单 元，处理单元和局部内存的多个处理器组成，多个 处理器之间通过共享内存或者通信网络相连接。 MIMD可以处理互相独立的多个任务或者协同执行 同一任务。MIMD体系结构中，如果处理器之间交 互通信频繁，称为紧耦合系统，反之为松耦合系统 。 106.2.2 并行检索的体系结构v检索系统利用MIMD计算机的一个简单的方式就是 采用多任务处理模式。并行计算机中每个处理器运 行一个分离的、独立的搜索引擎。搜索引擎并不协 同处理单个查询，但它可能共享代码库、文件系统 缓冲或共享内存中的数据。用户提交给搜索引擎的 查询由一个中介器进行处理，这个中介器从终端用 户那里接受检索查询，而后将这些查询分发给各个 搜索引擎。随着系统中处理器的增加，运行的搜索 引擎也越来越多，因此可以并行处理更多的检索查 询，系统地吞吐量提高，但单个查询速度没有改变 。 v尽管这一方法简单，但是随着处理器增加，磁盘和 I/O通道数量也增加，磁盘瓶颈会影响检索性能。 116.2.3 并行检索技术（一）并行检索策略 v并行技术分为数据并行和功能并行（控制并行）。在 SIMD计算机系统中，并行性一般只体现为数据并行， 即计算机内包含一组处理单元，每个处理单元存储一个 或多个数据元素。当计算机执行顺序程序时，可对全部 或部分的内部处理单元所存的数据同时操作。在MIMD 计算机或分布式计算机系统中，既可以采用数据并行， 也可以实现功能并行。此时的数据并行理解为数据库中 的各数据集分存于多个处理器及计算机中，它们可同时 对各自存储的数据集执行相同的操作。功能并行是将一 个程序划分为若干个段，每一段由一台处理机或计算机 执行，而多段程序并行执行需要考虑段间同步、通信等 许多复杂问题。126.2.3 并行检索技术（一）并行检索策略 v数据级并行依赖于并行处理机，特点是重复设置许 多个同样的处理单元，按照一定的方式相互连接， 在统一的控制部件作用下，各自对分配来的数据并 行地完成同一指令所规定的操作。控制部件实际上 是一台高性能的单处理器,它执行控制指令和只适 于串行处理的操作指令,而把适于并行处理的指令” 播送”给所有的处理单元,但仅有那些处于”活动”状 态的处理单元才并行地对各自的数据进行同一操作 .136.2.3 并行检索技术（一）并行检索策略 v功能并行主要表现于多个任务或多个程序段之间， 执行时可能存在着数据交往或控制依赖，因而解决 起来较为复杂。但是随着并行技术的进一步发展， 程序的控制并行间题将得到逐步解决。 146.2.3 并行检索技术（二）并行检索软件技术 v软件中的并行性主要是指程序的相关性和网络互连 。 v程序的相关性分为数据相关、控制相关和资源相关 ：数据相关说明的是语句之间的有序关系，控制相 关指的是语句执行次序在运行前不能确定的情况， 资源相关与并行事件利用整数部件、浮点部件、寄 存器和存储区等共享资源时发生的冲突有关。 v网络互连使用静态或动态拓扑结构网络。静态网络 由点点直接相连而成，这种方式在程序执行过程 中不会改变；动态网络可动态地改变结构，使之与 用户程序中的通信要求匹配。156.2.3 并行检索技术（三）并行检索硬件技术 v硬件技术方面主要从处理机、存储器和流水线三个 方面来实现并行。 v处理机系列包括CISC、RISC、超标量、VLIW、 超流水线、向量以及符号处理机。 v存储设备按容量和存取时间从低到高可分为寄存器 、高速缓存、主存储器、磁盘设备和磁带机五个层 次 v流水线技术主要有指令流水线技术和运算流水线技 术两种。 166.2.4 并行检索中的索引文档处理 （一）倒排表索引结构 v在并行处理的机器上进行检索要考虑到搜索算法对并行 处理能力的影响.一些主要的并行技术包括人物分配、 负载平衡和树排序等。任务分配技术通过均衡任务分工 ，保证并行系统在降低处理器的闲置时间和减少系统不 必要的开销之间达到平衡。任务分配技术则运用在并行 窗口搜索算法和分布式树搜索算法上。在并行系统中， 如果一个处理器在其他处理器之间完成了工作，那它就 会闲置下来，负载均衡技术就是用来激活闲置的处理器 。在搜索模型为树的搜索空间上搜索，采用的是从左到 右访问子节点的深度优先搜索法，但如果要找的信息处 于树的右边，则需要搜索大量的节点。树排序技术就是 采用一种算法来对搜索空间进行重新排序，从而加快查 找速度。176.2.4 并行检索中的索引文档处理 （一）倒排表索引结构 v检索系统通常采用倒排表（inverted file）索引结 构，可直接从关键词映射到所在文档。186.2.4 并行检索中的索引文档处理（二）基于倒排表的分割处理 v并行检索策略采用数据集合分割和查询项分割时，采用 倒排索引结构的检索系统需要在原始倒排表基础上进行 多种转换。 v使用倒排表进行数据集分割有两种实现方法：物理倒排 表分割方法和逻辑倒排表分割方法。这两者的数据集都 在物理上分成多个子集合。 v物理倒排表分割和逻辑倒排表分割的不同之处在于，前 者不仅将数据集分割，而且将倒排索引表也同时进行分 割，每个数据子集拥有自己独立的索引倒排结构。对于 逻辑倒排表分割，倒排索引表物理上并不进行分割，而 是增加一个处理机分配表，整张倒排索引表则被多个处 理器共享使用。 196.2.4 并行检索中的索引文档处理（二）基于倒排表的分割处理 v物理倒排表分割后，每个子集合具有自己独立的倒 排表结构，因此可以供不同的处理器单独使用，相 对灵活。但是，由于独立的倒排表没有全局的统计 信息，所以对每个子集进行检索时必须要另外的处 理来获得全局信息。方法通常有两种，一种是采用 复制的方法，将全局信息复制多份到每个独立的索 引倒排表上去；另一种是在每个子集合检索时分两 步，第一步获取全局信息，第二步进行检索。前一 种比较耗费空间，对索引表的更新也比较复杂；后 一种需要较大的通信开销。206.2.4 并行检索中的索引文档处理（二）基于倒排表的分割处理 v使用倒排表进行查询项分割时，要将每个关键词项 分割到不同的处理器上去。对于倒排表来说，就是 将关键词项表进行分割，分别对应在不同的处理器 上去。在进行查询时，查询项将被分解成多个关键 词查询，每个关键词对应不同的处理器分别进行处 理，处理结果按照查询的语义进行合并。216.2.4 并行检索中的索引文档处理（三）SIMD机器上的倒排检索 vSIMD机器也称阵列处理机，是由大量相同的互连 的PE（处理单元）对分配来的数据并行执行同一指 令所规定的操作。由主文档建立倒排索引可利用 CU（控制部件）执行建库程序而完成。这就要求 把该索引表数据合理地分配到各个PE的局部存储器 中，或按一定规律合理分配到各个存储体中。 v对提问编辑与变换后形成的检索指令表，因其中某 些广义检索指令基本上属于向量类指令，故需“播 送”给各个PE，由它们并行地执行该指令规定的操 作，而对其中的标量指令则由CU自己执行。 226.2.4 并行检索中的索引文档处理（四）MIMD机器上的倒排检索 vMIMD机器也即多处理机系统，它既可以是多台处理机 共享一个主存的紧耦合多处理机，也可以是不共享同一 主存的松耦合多处理机，能够实现作业、任务、指令、 数组各级全面并行。在此硬件环境下，倒排索引及主文 档可以分割存放，如倒排索引分放在内存各部分，主文 档分放在并行辅存中，以便在检索时由各台处理机同时 查找数据。对于共享主存的场合，必须解决好倒排索引 数据在各存储器模块中的定位与分配，以降低多台处理 机同时访问一个存储体时的冲突概率。对于不共享主存 的情况，应确保在每个处理机所带的局部存储器内存存 放各自常用的倒排索引，以免因分配不合理导致查不到 的现象。236.2.4 并行检索中的索引文档处理（五）并行顺排检索 v假若由p台处理机构成多处理机系统，处理由n个提问 构成的批量提问检索，则相应有两种处理方案。 v一、将顺排文档分散存放在共享或不共享的存储器中， 检索时，先将p个提问依次读入p台处理机，各自变换 为提问展开表，得到前p个提问的检索结果后，接着读 入p+1 2p个提问，直至所有提问处理完毕。 v二、将n个提问同时读入每一台处理机中，p台处理机 各自将每个提问展开，再将与其有逻辑联系的每篇文献 编制成检索标识表，经重复变换和比较，每台处理机获 得部分检索结果，最后将p组结果组合起来。 246.3.1 分布式信息检索原理16.3.2 分布式检索处理技术26.3.3 分布式信息检索模式 336.3.4 分布