分布式并行信息检索相关技术研究

分布式并行信息检索相关技术研究张青峰南开大学信息技术科学学院天津300071摘要当今社会，爆炸性增长的网络信息不但给用户提供了丰富的知识来源,同时也给检索系统带来了巨大的挑战。并行技术和分布式技术是解决这种大规模信息检索问题的关键技术，分布式并行信息检索是分布式并行计算技术在信息检索领域的应用。本文介绍了并行检索技术和分布式检索技术的基本概念、原理和方法，并对信息检索中的查询性能预测进行了介绍，主要论述了查询性能预测的主要方法和关键技术，最后讨论了分布式并行信息检索面临的一些挑战，并对未来的研究工作进行了展望和分析。关键字信息检索,并行检索，分布式检索，查询性能预测1引言当今社会，爆炸性增长的网络信息不但给用户提供了丰富的知识来源,同时也给检索系统带来了巨大的挑战。在信息爆炸的大数据时代，搜索引擎索引页面通常能够达到几十亿个到上百亿个,虽然单台计算机的处理能力不断提高，但是要对大规模海量的信息数据进行检索，单台计算机的处理能力毕竟有限，传统的基于单机的集中式信息检索技术已无法满足这种以大规模数据集为基础的并发多用户信息检索的需求，因此特别需要多台计算机进行“团队作战”。而并行计算和分布式计算能够利用多台计算机或者多个处理器的计算或存储资源来解决大规模数据问题。因此，很自然地会想到将并行处理或者分布式处理技术引入到信息检索当中，由此产生了分布式并行信息检索技术。分布式并行信息检索是分布式并行计算技术在信息检索领域的应用，是计算机技术与网络通讯技术的有机结合，它将分散的计算机资源统一整合，以发挥集群优势为目标，实现高速网络环境下的快速信息检索。在大规模数据检索中，并行处理具有较大的潜力可以挖掘，利用分布式系统，可以实现多条查询之间的并行检索以及单条查询内部的并行处理，由此提高整个系统的检索效率。本文的组织如下：第二节介绍并行计算、并行检索的基本概念、原理、方法和相关的进展；第三节介绍分布式计算、分布式检索的基本概念、原理、方法和相关进展；第四接介绍了信息检索性能预测相关方法；最后是对未来研究方向进行展望和分析。2并行检索2.1并行计算并行计算指的是，将单个问题划分为多个较小的“子”问题，用多个处理器同时分别处理这些“子”问题来得到单个问题的解。显然，由于并行计算能够同时利用多个处理器资源，所以通常能够减少问题求解的总时间，从而解决大规模的问题。多个可以同时工作的处理部件或处理器构成的计算机系统，称为并行计算机。并行计算系统包括并行计算机或多处理机系统。在并行计算系统中，不同处理器同时运行多个程序或者一个程序的不同进程，从而提高系统的运算速度。并行计算通过“以成本换时间”的方式来减少求解问题的总时间。总时间取决于时间最长的那个“部分”问题的求解。通过并行计算，系统具有较好的可伸缩性。根据指令和数据流的数目不同，并行计算的体系结构通常可以分成SISD、SIMD、MISD、MIMD等四种类型。其中MIMD是现在最通用和使用最广泛的一种类型。后面提到的并行检索也主要基于这种体系结构。MIMD并行体系结构主要由多个具有自己的控制单元、处理单元和局部内存的多个处理器组成，多个处理器之间通过共享内存或者通信网络相连接(图中以粗黑线表示)。MIMD可以处理互相独立的多个任务或者协同执行同一个任务。MIMD体系结构中，如果处理器之间交互通讯频繁，则称为紧耦合(tightlycoupled)系统；反之，则称为松耦合(looselycoupled)系统。2.2并行检索要实现并行检索，首先让我们考察信息检索的一般过程：如图所示，用户提交一条查询，代理程序(broker)对原始查询进行处理(如查询的分析转换或格式化处理等等)，然后将处理后的查询发给搜索程序，搜索程序找到结果并进行处理(如排序)后返回给代理，代理经过必要的处理(如结果的归整、合并等)将结果返回给用户。从以上可以看出，信息检索有并行处理的潜力可以充分挖掘。根据对象的不同，并行检索总体上可通过以下两种方式实现并行：1.多条查询之间的并行处理。一个最自然的想法就是利用MIMD结构对多条查询的处理并行化，即每个处理器处理不同的查询，每个查询的处理之间相互独立，最多只对共享内存内的部分代码或者公有数据实行共享。这种方法也称为任务级的并行检索。它可以同时处理多个查询请求，从而提高检索的吞吐量。上图显示了3条不同查询在3个处理器上的并行处理过程。每条查询通过代理(也可同时运行多个代理程序，每个代理分别处理一条查询)发送到不同搜索程序(每个处理器上运行一个搜索程序)上去执行，每个搜索程序的结果通过代理返回到不同查询的发起者。如果MIMD由多台具有自身处理器和磁盘的计算机组成，每台机器执行自己的搜索程序，并且只访问本地的磁盘，则没有硬件资源访问冲突问题。但如果多个搜索程序访问的是相同的磁盘资源，则可能存在磁盘存取冲突问题。这时可以通过增加磁盘或采用类似Raid磁盘阵列的方法来减少冲突，但同时不免加大硬件设备的开销。另外一些可能的方法包括复制访问频繁的数据到不同磁盘以降低访问冲突、将数据分割到多个磁盘等等。查询间并行化策略是从一般检索升级到并行检索的最简单方法。简单地说，就是将检索系统复制多份(数据可以复制也可以不复制)，每份分别处理不同的查询请求。当然，这种升级硬件资源消耗比较高。而且，简单地堆积硬件资源并不一定就可以提高信息检索的效率，必须考虑硬件资源的访问冲突，设计合理的软件结构和访问策略，才能提高信息检索的总体性能。2.单条查询内部的并行处理。即对单条查询的计算量进行分割，分成多个子任务，并分配到多个处理器上的搜索进程上去执行。这种检索也称为进程级并行检索。将单条查询分成多个子任务的方法通常有两种：一种称为数据集分割，它是事先将数据集分割成多个子集合，对同一条查询分别查询多个子集合数据，然后将每个子集合上的结果合并成最终结果；另一种称为查询项分割，它是将查询分解成多个子查询(如将一个多关键词查询分成多个单关键词查询)，对每个子查询分别查询数据集，得到部分结果，并将部分结果合并成最终结果。上图给出了一个单条查询内部并行处理的示意图：查询发送给代理程序，代理程序将一条查询划分成多条子查询，每条子查询分别发送给一个搜索进程进行处理，各进程返回的子结果在代理上进行综合，得到最后的总结果返回给用户。在进行查询之间的并行时，信息检索系统中的数据结构通常不需要改变。而对于单条查询内部的并行处理，则需要对原有串行信息检索的数据结构做相应的改变。在信息检索系统中通常采用一种称为“倒排表”(invertedfile)的索引结构，可以直接从关键词映射到所在文档。并行检索策略采用数据集合分割和查询项分割时，采用倒排表索引结构的检索系统需要在原始倒排表基础上做多种转换。使用倒排表进行数据集分割有两种实现方法：物理倒排表分割方法和逻辑倒排表分割方法。这两者的数据集都在物理上分成多个子集合。物理倒排表分割和逻辑倒排表分割的不同之处在于，前者不仅将数据集分割，而且将倒排索引表也同时进行分割，每个数据子集拥有自己独立的索引倒排结构。对于逻辑倒排表分割，倒排索引表并不物理上进行分割，而是增加一个处理机分配表，整张倒排索引表则被多个处理器共享使用。物理倒排表分割后，每个子集合具有自己独立的倒排表结构，因此可以供不同的处理器单独调用，相对比较灵活。但是，由于独立的倒排表没有全局的统计信息(在进行检索时通常需要全局的统计信息来计算文档和查询的匹配相似度)，所以对每个子集进行检索时必须要有另外的处理来获得全局信息。方法通常有两种：一种是采用复制的方法，即将全局信息复制多份分配到每个独立的索引倒排表上去；另一种是在每个子集合检索时分两步走，第一步获取全局信息表，第二步才进行检索。前一种方法比较耗费空间，对索引表的更新也比较复杂；后一种方法需要较大的通讯开销。总的来说，逻辑倒排表分割方法的通讯开销很小，因此总体性能会高于物理倒排表分割，但是必须要对普通倒排表增加额外的数据结构来进行转换。而物理分割方法的灵活性比较强，每个文档子集可以单独检索。通过物理分割的方法，很容易将非并行的信息检索系统转换为并行的检索系统。使用倒排表进行查询项分割方法时，要将每个关键词项分配到不同处理器上去。对于倒排表来说，就是将关键词项表进行分割(逻辑的或者物理的)，分别对应到不同的处理器上去。在进行查询时，查询项将被分解成多个关键词查询，每个关键词对应不同的处理器分别进行处理。处理结果按照查询的语义进行合并。例如，如果是多个关键词布尔表达式查询(如：查询：“并行”AND“检索”)，则合并的主要工作是进行布尔操作。如果是需要对多个子结果进行排序，则合并的主要工作是评分归一化并排序。相对而言，数据集分割方法能够提供更简单的倒排表构建和维护。Jeong和Omiecinski通过实验对这两种方法进行了比较：假设每个处理器有自己的I/O通道和磁盘，当关键词出现在文档和查询中的分布呈偏态分布(skewed)时，采用数据集分割的方法性能较好；而当关键词在查询中呈均匀(uniform)分布时，查询项分割方法更优越。除了倒排表以外，信息检索中常用的其他数据结构(如签名文件signaturefile、后缀队列suffixarray等)在应用到并行检索时也需要进行改变。另外，当检索系统使用其他并行结构(如SIMD)时，也需要对数据结构做相应改变。3分布式检索3.1分布式计算分布式计算可以把地理位置上分布更广的异构文档整合成一个更大的逻辑整体。分布计算是利用网络连接的多台计算机去求解一个问题。从广义上说，分布式计算可以看成MIMD并行计算的一个特例。不过所不同的是，分布式计算中的通讯开销比较大，因此最多只能算是一个松耦合的并行计算系统。另外，它能够把更大范围的异构数据整合成一个逻辑整体，因此，分布式计算具有更强大的计算能力。3.2分布式检索利用分布式计算进行信息检索称为分布式检索。与并行检索比较，分布式检索的主要特点在于：一、分布式检索通常处理的是地理位置分散的异构数据，不同地理位置计算机系统间通讯的开销比较大，因此，分布式检索中应该尽量避免不同地理位置计算机系统之间的通讯操作。就通讯本身而言，由于不同系统的异构性，分布式检索系统中通常采用TCP/IP协议来实现通讯，而并行检索中处理器之间的通讯可以通过共享内存来实现。二、分布式检索的数据规模相对较大，每个节点的处理能力又不尽相同，因此，分布式检索通常只选择某些数据子集进行检索，而不是像并行检索那样，需要返回每个数据子集的结果。三、分布式检索的对象的异构性使得统一描述和访问成为必须要考虑的问题。由于第一个特点，分布式检索通常采用数据集分割而不是查询项分割来划分数据。因为，采用查询项分割后进行信息查询需要更多的通讯操作。由于第二个特点，需要研究分布式检索中数据集合的划分和子集合的选择方法。数据集合划分的方法很多。一个最简单的方法就是将数据集合按照语义类别(比如：军事、体育等)划分成子集合，在进行查询时，选择相应的语义类别对应的子集合进行查询。在进行数据集划分时可以采用分类或者自动聚类方法。在进行查询时，首先根据查询和每个子集合的相似度来将所有数据子集合进行排序，选择部分子集合进行查询，然后将每个子集合上返回的结果进行合并而得到最后结果。计算查询和数据子集合的相似度可以采取以下一些办法：1)将整个数据子集看成一个大文件直接和查询进行相似度计算，选择相似度高的子集合进行查询；2)将整个数据子集看成由多个块组成的集合，分别计算查询和每个块的相似度来得到查询和整个数据子集的相似程度；3)通过训练，得到每个数据子集对应的一个查询内容模型，直接将查询和这些查询内容模型相匹配得到相似度。在每个数据子集上得到的结果必须合并才能得到最终的结果。由于第三个特点，分布式检索中要研究异构文档描述、访问和结果返回的标准化问题。这包括两个方面：一方面是异构数据的描述、查询请求和查询结果的表达问题，可以通过标准(元数据和文档描述标准)的建立来支持异构数据的互通；另一方面是检索中的互操作问题，可以通过定义统一的分布式检索的互操作协议来共同支持查询语义和语法。其中，最