并行信息检索及其控制过程，本文主要内容关键词为：信息检索论文,过程论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
中图分类号 G354.4文献标识码 A文章编号 1007-7634（2004）08-0985-04
1 并行信息检索的作用
并行信息检索主要依赖并行处理技术。并行处理是指把计算机任务划分成更小的任务，然后用多个处理器并行执行子任务。每个处理器处理同一个问题的不同部分。
通过并行的计算方法，可以大大的缩减解决问题所需的整体时间。只要问题可以被继续分解成更小的部分，并且这些部分可以并行的运行，那么就可以通过增加系统处理器减少运行时间。
随着因特网的发展，网络信息资源的数量迅速增长，网络信息检索系统的运转速度越来越引起人们的关注。在一些检索中，用户无法忍受漫长的检索等待时间。这就对信息检索系统的运行速度和高效性提出了更高的要求。为了提高信息检索系统的响应时间，并行检索的技术应运而生。
很多人都认为并行技术是解决检索系统运行速度的一个有效的解决方案，并尝试在文本检索系统中运用并行处理技术。这些尝试主要针对提高检索效率，包括检全率和检准率，以及串行处理器相比可以大幅度的提高反应时间，把对用户的反应时间控制在一个相对可接受的时间范围之内。
2 并行信息检索的结构类型
Flynn于1972年提出了一个并行结构的分类方式，这种方式是根据CPU所控制的“流”来进行分类的。这些“流”既可以是系统指令，也可以是指令所控制的数据。尽管这种分类方法没有考虑到输入/输出及指令设置，但它还是最流行的并行结构分类。这种方法把并行结构分成4类，即SISD（单指令单数据流）、MISD（多指令单数据流）、SIMD（单指令多数据流）和MIMD（多指令多数据流）。其中，SISD是通常的顺序结构的冯·诺依谩机器。而MISD用n个处理器来操作一个数据流。每个处理器都执行自己的指令流，这样多项操作就在一个数据项目上运行。SIMD结构是用同一指令并行操作不同的数据，因而是一种并行数据计算。它的指令需要传递给结构中的n个处理器。使用这种结构的系统通常拥有大量的并行计算机，而这些计算机上都有相对简单的处理器，控制所有同步处理操作的控制单元。处理器之间可能共享存储器，也可能每个处理器都有自己的本地存储器。这种结构在信息检索的并行计算中占据主要地位。MIMD结构较SIMD复杂，其中处理器之间是独立的，对不同的数据执行不同的指令。MIMD是目前并行引擎所使用的主要结构。该结构通常还包括共享的存储器或者一个通信网络。
3 并行检索的算法
不同的并行结构使用不同的检索算法。其中使用较多的是MIMD及SIMD结构中所使用算法。
3.1 MIMD结构的算法
MIMD结构的灵活性很大。用这种结构建立检索系统最简单的方法是使用。这种并行计算机的每个处理器运行独立的搜索引擎。搜索引擎并不是合作地处理各个查询，但是它们共享代码库以及数据，并由代理来管理用户查询，以及搜索引擎的提交过程。代理从终端用户收集检索需求，然后在各个搜索引擎之间进行传递。随着系统中处理器的增加，系统运行的搜索引擎的数目增多，这样就可以并行的处理更多的搜索请求，进行增加了系统的吞吐量。这种方法需要在系统的资源之间进行合理的平衡。特别是当处理器的数量增多后，磁盘以及输入输出通道也应增加。除非主存储器能够存储整个的检索索引，否则在不同的处理器上运行检索处理将会引起磁盘访问权和输入输出资源的竞争。硬件方面的瓶颈将会很大程度上影响性能，也会削弱增加更多的处理器所应获得的更多吞吐量。
为了加速查询反应时间，该算法把一个简单的查询分割成子任务，然后在多个处理器之间进行分配。如图1所示。在这种构造中，代理和检索处理过程并行运行，互相合作来完成同一个查询。其中系统中高层次处理过程为：代理从终端用户接受一个查询，分发给各个处理过程。然后每个处理过程完成查询工作的一部分，并且把中间结果返回给代理。最后代理把中间结果联合成最终的结果返回给用户。
图1 代理和检索处理过程
由于检索是通过将大量数据分成小块来实现的，所以如何划分算法就变成了如何分割数据的问题。图2所示的是使用典型搜索算法数据加工的高层视图。其中d[，j]代表文档j，k[，i]代表索引项i；索引项可以是一个词、一个段落、一个概念或是更抽象的内容。w[，ij]是权重。图2中的结构说明了两种数据划分形式。一种是文档划分，行向分割数据矩阵，把文档在各个子任务自己进行划分。集合中的N个文档分配给系统中P个处理器，产生了P个子集合，大约每个子集合中有N/P个文档。在查询处理阶段，每个并行处理过程在自己的子集合中执行查询，最后把每个子集合的结果连接成最终的结果列表。另一种方式是词划分，纵向分割数据矩阵，把索引项在P个处理器之间进行划分，这样每个文档的查询程序就分布在系统的多个处理器中。
图2 搜索算法的数据结构
（1）文档数据的划分。
在文档中需要进行词的划分。划分可以是对逻辑文档划分，也可以是对物理文档划分。逻辑文档划分是使用与原顺序算法基础相同的倒排文档索引，把倒排档扩展到与其相关连的每个并行处理中。通过扩展每个词的字典条目，使它包含P个指针，指向相关的倒排列表。其中，第j个索引指针的文档条目块与第j个处理过程相连接。
向系统提交一个查询时，代理首先保证共享存储器中有需要的词表字典以及倒排档条目，从而使所有并行处理过程访问一个共享复本。然后，代理初始化P个并行处理过程。通过扩展字典访问倒排档中的相关条目，每个处理过程在相应的子集上执行相同的算法。由于查询过程中的所有文档操作都是只读的，在处理过程中所访问的字典并不需要加锁。搜索过程的作用是在一个共享文档值的累计队列中记录文档值，过程结束时通知代理。更新累积队列不需要加锁操作，这是因为不同的搜索过程是互斥的。所有的搜索过程结束以后，代理根据文档值的累计情况来对队列进行分类，然后产生一个最后的文档排队列表。
物理文档划分是文档划分的第二种方法，其中文档被物理地分割成独立的、自包含的子集。每个并行处理器都有一个这样的分割。每个子集又有子集的倒排档，并且搜索处理过程中不存在任何共享行为。当向系统递交一个查询的时候，代理把这个查询分发所有的并行搜索过程。每个并行搜索过程在自己的文档集合中对查询进行匹配，产生一个本地的中间命中列表。然后代理从所有的并行搜索中搜集所有的中间命中列表，合并成最后的命中列表。
该合并过程的一个前提是：并行搜索过程生成了全局一致的文档值，而这些文档值可以直接合并。由于依赖所使用的排序算法，每个并行搜索过程可能需要全局词统计，这就会产生全局一致的文档值。收集全局词统计信息的方法有两种：一种是在索引时间上计算词统计，然后用每个子集来为这些统计记分。另一种是把查询处理分两个阶段进行。在第一个阶段中，代理从收集每个搜索过程中收集子集的词统计，然后把他们合并成全局词统计。第二个阶段中，代理把查询以及全局词统计分发给检索过程以及前面的检索匹配过程。第一种方法提供了更好的查询处理性能，但是以更复杂的索引为代价；第二个方法建立一个子集，然后独立的对它进行维护，这是以查询匹配中的双倍通信为代价的。
为物理划分文档而建立倒排档，每个处理器并行生成了自己的完整索引，并且和其文档划分相对应。如果全局集合统计存储在独立的字典中，则必须执行一个合并步骤，该步骤为所有的分割累积全局统计，然后把它们分发给每个分割字典。
逻辑文档划分比物理文档划分需要更少的通信开销。因此可能提供更好的整体性能。但物理文档划分提供了更好的灵活性，更容易把现有的信息检索系统转换成并行信息检索系统。无论哪个方法，线程为检索过程、控制操作、以及互相之间的交流提供了方便的程序范例。通过使用并发执行、交流、以及同步操作的相关提取过程，线程包允许程序员开发并行程序，并且高效地操作系统服务以及共享存储器。
（2）标识文档。
如果系统使用标识文档，为完成系统的文档划分需把文档在处理器之间进行分割，并且每个处理器生成了它的文档划分标识。在查询的时候，代理为每个查询产生一个标识，并把它发送给所有的并行处理器。每个处理器在本地对查询标识进行匹配。然后，把结果返回给代理，代理把这些结果合并成一个最后的命中列表。对于布尔查询，最后的结果仅仅是每个处理器返回的结果的并集。对于排序查询，排序的命中列表将会像倒排档中的处理方式来进行合并。
3.2 SIMD结构
SIMD结构的算法既可建立在标识档结构之上，也可建立在倒排档结构之上。典型的SIMD系统是Thinking Machines CM-2。CM-2使用分离的前端主机来为后端的并行处理元素提供用户界面。前端主机控制后端数据的加载以及卸载，并且执行连续的程序指令，例如条件和循环语句。并行宏指令是从前端发送到后端微控制器的，微控制器控制后端处理元素集合的并发操作。CM-2既支持基于标识档的信息检索算法，也支持基于倒排档的信息检索算法。
（1）基于标识文档的检索。
检索过程分为几个步骤。首先，检索系统为每个检索词构建一个标识。其次，系统把查询标识和集合中的每个文档的标识进行比较，然后对匹配的文档进行标识，把它作为潜在相关的文档来处理。最后。系统对这些潜在相关的文档进行全文扫描，剔除不匹配的，把相关的文档进行排序，然后把结果返回给用户。同样的，如果系统处理的是布尔查询，那么就需要为每个查询生成不只一个标识，还要根据查询中所使用的操作符把中间结果连接起来。
ProbeDoc（PBit DocSig[]，Char * term）
｛
iht i；
Pint DocMatch；
DocMatch=1；
for（i=0；i＜NumHash；i＋＋＝｛
DocMathch &=DocSig [hash（i，term）]；
｝
return DocMatch；
｝
这是一个应用在CM-2的核心子程序。这个程序为给定的查询词“term”探测文档标识DocSig，对每个“term”应用标识hash函数，然后把DocSig中相应的位相加，结果存到在DocMatch中。如果DocMatch等于1，那么“term”在DocSig中出现了；如果DocMatch等于0，那么“term”没有出现。DocSig和DocMatch都是并行变量，这样每个虚拟处理器都并行的在自己的变量副本中进行操作。通过把整个的标识文档加载到后台虚拟处理器，所有的文档标识符都可以并行的检索了。
（2）基于倒排档的检索。
SIMD结构中的倒排列表中包含每个文档中检索词所出现的位置。位置是一个有序集合＜k[，i]，d[，j]＞，其中k[，i]是词标识符，d[，j]是文档标识符，由于检索模式的不同，位置还可能包含权值或者位置信息。如果存储了位置信息，那么每次k[，i]出现在d[，j]中都会产生一个位置。
CM-2中的并行倒排档使用两个结构来存储倒排档数据：一个位置表以及一个索引。位置表包含了文档标积以及位置表中相应条目的索引。这些结构在加载数据之前，通过词标识对位置进行分类，然后按照这种分类方式把文档标识符加载到位置表，填充到长度为P的行序列中，P是正在使用的处理器数量。位置表被看作是并行序列。对于每个词而言，索引存储了位置表中第一个和最后一个条目的位置。
在检索阶段，使用这些数据结构对文档进行排序：首先检索系统向后端处理器加载位置表，然后系统对每个查询词进行循环操作。对于每个查询词，返回需要被处理的位置表条目的范围。检索系统再对该范围内的行进行循环操作。包含当前词条目的处理器被激活，并且使用相应的文档标识符来更新相关文档值。
文档值是在累积器中建立的，它被分配到一个并行序列中。为了针对个别文档更新这个累积器，需要确定累积器的行以及行内位置，该信息可存储在位置表中。此外，还需要为每个位置分配权值，并将该权值存储在位置表中。下面是计算一个加权词值的算法。
scoreTerm（Pfloat DocScore[ ]，Pposting Posting[]，termT erm）
｛
int i；
int firstPos；
int lastPos；
Pint DocRow；
Pint DocPos；
Pfloat Weight；
for（i=term.firstRow；i＜=term.lastRow；i＋＋＝
firstPos=（i==term.firstRow？Term.firstPos：0）；
lastPos=（i==term.lastRow？Term.lastPos：N_PROCS-1）；
where（Position＞=firstPos ＆＆ Position＜=lastPos＝｛
DocRow=Posting[i].row；
DocPos=Posting[i].pos；
Weight=term.weight*Posting[i].weight；
[DocPos]DocScore[DocRow]＋=Weight；
｝
｝
｝
scoreTerm程序假定已经完成了对索引词的查找，且查找结果存储在“term”中。程序循环遍历每个与检索词有关的位置行，确定在当前行内需要处理哪个位置点。“Position”是一个并行的整数常量，范围在0～N_PROCS—1之间。它在where子句中的作用是激活当前行位相应的处理器。
到目前为止，并行算法的理论研究还不是很充分。大多数的并行算法主要针对个别的系统。这样就限制了并行算法的发展以及在实际中的应用。另外，并行算法的主要瓶颈在于如何对输入输出设备和处理器进行平衡，并不是单纯的增加处理器的数量就能够提供系统的运行速度。这样，在理论上对并行检索的算法做进一步的研究，设计能够独立于硬件，而较大幅度提高系统运行速度的方法。此外，在输入输出设备方面的配置和处理器之间找到一个平衡点，最大限度地发挥硬件资源，减少输入输出设备在并行检索中的限制也是研究的一个重要内容。