1、第8章 并行和分布式信息检索第8章 并行和分布式信息检索8.1 并行信息检索8.2 分布式信息检索8.3 元搜索引擎8.4 P2P网络信息检索8.5 小结思考题第8章 并行和分布式信息检索8.1 8.1 并行信息检索并行信息检索8.1.1 8.1.1 并行计算的概念并行计算的概念并行计算就是研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，分配给多个计算机进行处理，并把这些计算结果综合起来得到最终结果的问题。并行计算技术起源于科学计算，但如今其应用领域已不再仅仅限于科学计算。它已经被广泛地应用在工程计算及许多新兴的应用领域，比如金融走势模拟分析、信息检索和数据挖掘等。第8章
2、并行和分布式信息检索并行计算机是由多个可同时工作的处理器构成的计算机系统。目前，并行计算系统主要是指并行计算机(Multicomputer)系统或多处理机(Multiprocessors)系统。在一个并行计算系统中，不同处理器同时运行同一程序的多个任务或进程，或者同时运行多个作业或大量计算问题的多个独立程序，以提高系统的运算速度、吞吐量、系统的可靠性或有效地利用系统的资源。就处理器的组合方式不同，可以对并行体系结构进行分类。常用的Flynn 分类法根据指令和数据流数目，把并行计算体系结构分为四种类型：(1)SISD(单指令、单数据流)：串行地执行指令；(2)MISD(多指令、单数据流)：在多个
3、处理机中用不同的指令去处理单个数据；第8章 并行和分布式信息检索(3)SIMD(单指令、多数据流)：以多个处理机同时对不同的数据执行同一种指令操作；(4)MIMD(多指令、多数据流)：以多个处理机自治地对不同的数据执行不同的操作。高速并行计算有三种类型的应用：计算密集型(Compute-Intensive)应用，如大型科学工程计算与数值模拟；数据密集型(Data-Intensive)应用，如数字图书馆、数据仓库、数据挖掘和计算可视化等；网络密集型(Network-Intensive)应用，如协同工作、遥控和远程医疗诊断等1。第8章 并行和分布式信息检索搜索引擎的设计和实现需要在短时间内存取和处
4、理海量数据，因此是一种数据密集型应用。这类数据密集型应用是并行计算技术非常适合的领域，同时也是必须采用并行计算技术的应用领域。例如，如果有总共达1 TB的文本数据，需要在这些特定的文本文件中找到“并行计算”这个词组，并要知道它出现了多少次，都出现在哪些文件的什么位置，并且要求系统给出答案的时间不超过1秒。如果用普通的计算机来处理，单单文件I/O，所需的时间就不止1秒；即使文件I/O的时间可以忽略不计，CPU以峰值速率运行，它要在1 TB数据中找到一个特定的词组所需的时间开销也是巨大的。再进一步，如果有成百上千用户同时利用系统搜索不同的词组，都要求在1秒钟内得到答案，单机系统根本处理不过来。第8
5、章 并行和分布式信息检索用户不能容忍过长的等待时间，如果磁盘的转速和寻道时间没有数量级的提高，那么将数据读入内存是唯一避免I/O瓶颈的方法。目前普通计算机无法提供1 TB的内存，那么可以考虑将 1 TB数据读入100台10 GB内存的计算机，100台计算机同时在总计1 TB的数据中查找，每台计算机仅仅查找10 GB数据，这样才有可能在短时间内完成用户的请求。并行计算，换来的是I/O带宽的累加，内存容量的累加以及CPU处理能力的累加。在搜索引擎这种海量数据处理问题上，并行计算技术是高效处理海量数据的根本办法。第8章 并行和分布式信息检索8.1.2 8.1.2 并行信息检索体系架构并行信息检索体系
6、架构在介绍并行检索之前，先看看信息检索的一般过程，如图8-1所示。图8-1 检索的一般过程第8章 并行和分布式信息检索如图8-1所示，用户提交一个查询，查询代理对查询进行分析，比如进行编码格式转换，分词解析等，得到一个规格化的查询词，发送到检索程序，检索程序从索引中查找文档并进行处理，如计算得分和结果排序等，然后将初步结果发回到查询代理，查询代理进行规整、合并后，把结果返回给用户。综上所述，信息检索可以很方便地进行并行化处理。直观地看来，多条查询之间可以进行并行检索，单条查询内部也可以进行并行检索。第8章 并行和分布式信息检索1 1 一般体系架构一般体系架构一种可行的体系架构就是，检索系统利用
7、并行计算机中的每一个处理器运行一个分离的、独立的搜索，这些独立的搜索可能共享程序代码库、文件系统中的数据或共享内存中的数据等。用户向搜索引擎提交的查询是由一个代理程序来管理的，代理接受用户的搜索请求，并把请求分发到子检索系统中。图8-2所示为原理模型，图8-3为对应的并行信息检索服务器模块图。第8章 并行和分布式信息检索图8-2 并行检索模型第8章 并行和分布式信息检索图8-3 并行信息检索服务器第8章 并行和分布式信息检索如果有较多的处理器，就可以并行运行更多的独立搜索，因此可以并行处理更多的搜索请求，提高系统的吞吐量。但是需要注意，并不是简单地堆积CPU和磁盘，就可以提高信息检索的性能。问
8、题是如何有效地利用硬件资源，设计合理的软件结构包括系统体系结构和数据结构，以提高信息检索的性能。否则有时候盲目添加更多的硬件反而会降低性能，因为随着处理器数目的增加，磁盘和I/O通道访问次数也随之增加，各个处理器的访问可能会互相冲突，造成磁盘的存取竞争。磁盘瓶颈将会降低性能，抵消增加处理器带来的吞吐量增益。因此需要仔细地平衡系统中的硬件资源。第8章 并行和分布式信息检索2 2 数据分割和计算分割数据分割和计算分割为了支持并行检索，除了在计算机中增加更多的磁盘外，系统管理员还必须合理地在磁盘中分配索引数据。如果两个搜索进程需要存取存放在相同磁盘上的索引数据，仍然会有磁盘竞争的问题。增加磁盘的数量
9、，可以减少这样的竞争，但是同时也增加了存储设备的费用和更新的复杂性。可以考虑作一些改进，例如，将那些被访问次数多的数据复制存储，而把较少被访问的数据随机分布，这就是索引数据的分割和复制存放策略。第8章 并行和分布式信息检索为了进一步改善查询的响应时间，必须对单个查询所需要的计算量进行分割，分出多个子任务，并分配到多个处理器上去执行。在这种方法中，代理和搜索进程也是并行运行在分离的处理器上，但是现在是协同运行去处理同一个查询。代理程序接受用户的一个查询，并把它分配到多个搜索进程上。然后，每个搜索进程执行部分查询任务，把中间结果返回给代理。最后，代理把这些中间结果组合起来，形成一个最终的结果，交付
10、给用户。第8章 并行和分布式信息检索从上面的描述可以知道，并行检索主要涉及两大关键技术，一是并行计算，二是并行数据存取，前者需要通过并行编程实现检索计算的并行化，后者则是需要对数据结构如倒排文件进行分割，并存放在并行文件系统上，以提供高性能高带宽的并行数据存取功能。针对搜索引擎而言，这两大技术的实现有着很独特的要求和特点。下面主要介绍面向信息检索的并行编程和数据并行技术以及Google在这方面的两大核心技术：MapReduce并行编程模型2和GFS(Google File System)并行文件系统3。第8章 并行和分布式信息检索8.1.3 8.1.3 并行编程并行编程1 1 并行编程概述并行
11、编程概述并行编程模型一直是并行计算研究领域的重点内容，它和并行计算机体系架构紧密相关。共享存储和消息传递是目前两种主流的并行编程模型。共享存储体系架构下的并行编程模型主要是共享变量编程模型，它具有单地址空间、编程容易、可移植性差等特点，其实现有OpenMP4和Pthreads(POSIX Thread)5等。分布式存储体系架构下的并行编程模型主要有消息传递编程模型，消息传递编程模型的特点是多地址空间，编程困难，可移植性好，其实现有 MPI(Message Passing Interface)6和 PVM(Parallel Virtual Machine)7等。第8章 并行和分布式信息检索目前用
12、来构建搜索引擎的都是普通PC组成的集群(Cluster)系统，而不是具有共享存储的SMP(Symmetrical Multiprocessing)机器，因为后者比较昂贵。而集群系统是很典型的分布存储体系架构，因此需要采用分布存储编程模型，例如消息传递编程。消息传递(Message Passing)是指在各个处理机节点之间通过用户调用并行系统的子程序库来实现它们之间的实时消息传递(Message Communication)。消息传递可以定义为：在一组进程当中，各个进程之间通过发送和接收数据来实现进程之间的相互通信。数据的传递需要各个处理器节点之间相互协调操作，即一个发送(send)的操作就必须
13、有一个接收(receive)的操作与之相匹配。第8章 并行和分布式信息检索并行编程对开发者的要求较高。相比于串行编程，并行编程中需要额外考虑以下问题：(1)负载平衡问题。并行程序中可能出现负载不平衡的问题，没有充分利用每个处理器的处理能力，导致一些处理器比较空闲，影响了程序的总体执行性能。(2)进程数或线程数的选择问题。一些应用问题存在所需进程或线程数目与处理机数目不匹配的问题。若前者太小，则不能充分发挥机器的效率；若太大，又无法执行。第8章 并行和分布式信息检索(3)通信带宽和延迟问题。并行程序进程间的通信带宽和延迟问题可能会严重影响程序的执行性能。特别是在分布式存储系统如集群系统中，通信延
14、迟对总体性能的影响更大。(4)细粒度并行问题。编写并行程序时，一般并行粒度越小，越可以更好地利用多处理器，但并行粒度太小也会增加系统的管理开销。第8章 并行和分布式信息检索2 2 并行编程模型并行编程模型MapReduceMapReduce搜索引擎系统需要对原始数据(爬虫抓取下来的文档、用户查询日志等)进行处理，生成倒排索引文件，网页链接关系库等。这些处理算法原本是简单直观的，但在处理海量的原始数据集时，要在较短的时间内得到运算结果，就只有把运算分布到多台机器上并行进行。如何分割数据，如何并行运算，如何处理异常和错误，都需要进行详细的分析设计，这些都是很复杂的问题。第8章 并行和分布式信息检索
15、针对这种情况，Google搜索引擎开发人员提出了一种模型，称为MapReduce编程模型，把分布运算带来的细节问题，如数据分割、容错机制、负载均衡等封装在一个底层包里面隐藏起来，开发人员只需考虑接口，实现直观的算法。也就是说，基于MapReduce模型实现的程序可以自动分发到多个机器并行运算，由底层软件包进行数据分割、任务调度、错误处理以及相关的主机通信，使得没有任何分布式系统开发经验的人也可以利用分布式系统的巨大运算能力。MapReduce模型的核心是Map函数和Reduce函数，Map函数把输入的一个关键字/值生成多个临时关键字/临时值，作为中间结果；Reduce函数把Map函数产生的中间
16、结果作为输入，把具有相同临时关键字的多个临时值合并起来，得到最终结果，如图8-4所示。第8章 并行和分布式信息检索图8-4 MapReduce的任务处理流程第8章 并行和分布式信息检索在搜索引擎系统中，很多运算都可以用这个模型来表示。比如，统计一个页面的链入URL，可以用下面的Map函数和Reduce函数表示。Map函数为在source 页面碰到的每一个链接到target的链接，输出target，source；Reduce函数把target相同的输出合并起来，得到target，list(source)，它就是所有链接到target的网页集合。倒排索引的建立也可以用这个模型，Map函数分析每一个
17、文档，输出一系列的word，document ID；Reduce函数接受所有的中间结果，并根据documentID进行排序，得到word，list(document ID)。最后再把Reduce函数输出的结果集合起来，就是一个简单的倒排文件了。【例例8-18-1】统计一个文档集合中各个词出现的次数。解：解：可以用MapReduce方式编写，编程例子如下：第8章 并行和分布式信息检索 Map(String key，String value):/key：document name /value：document contents For each word in value:EmitInterme
18、dicte(w，1)；Reduce(String key，Iterator values):/key：a word /values：a list of counts int result=0;for each v in values：result+=ParseInt(v);Emit(AsString(result);第8章 并行和分布式信息检索在本例中，Map函数把遇到的单词和出现次数(这里为1)作为中间结果输出；Reduce函数把同一个单词的中间结果加在一起。MapReduce是一个并行编程模型，这个模型可以方便地处理实际问题，它隐藏了分布运算量进行并发运算后带来的数据分割、容错机制、负载均
19、衡等问题，极大简化了并行编程的复杂度。开发人员只要把算法描述为Map和Reduce函数，就可以自动利用分布资源，高效进行并行运算。第8章 并行和分布式信息检索8.1.4 8.1.4 数据并行数据并行在进行查询之间的并行时，检索系统中的数据结构通常不需要改变。而对于单条查询内部的并行处理，则需要对原有串行信息检索的数据结构进行相应的改变。检索系统中最重要的数据结构就是倒排索引。因此要考虑进行倒排索引分割。第8章 并行和分布式信息检索1 1 倒排索引分割倒排索引分割倒排索引分割可以分为两种，一种是基于文档的倒排索引分割(Document Partitioning)，另一种是基于查询项的倒排索引分割
20、(Term Partitioning)。基于文档的倒排索引分割有两种实现方法：物理文档分割(Physical Document Partitioning)和逻辑文档分割(Logical Document Partitioning)。逻辑文档分割需要对倒排文件进行扩展，让每个并行进程能够直接访问一部分索引，这些索引对应于处理器所要处理的那部分文档子集。物理文档分割则不仅将数据集分割，而且将倒排索引表也同时进行分割，每个数据子集拥有自己独立的索引倒排结构。对于逻辑文档分割，倒排索引表并不物理上进行分割，而是增加一个处理机分配表，整张倒排索引表则被多个处理器共享使用，如图8-5所示。第8章 并行和分
21、布式信息检索图8-5 逻辑文档分割8第8章 并行和分布式信息检索逻辑文档分割后的检索过程：用户输入查询，代理将所需词典词条和所有posting list放入共享内存，每个处理器负责访问各自的文档信息，进行相似度计算，最后将结果汇总。因为，多个处理器对索引的访问都是“读”操作，所以没有访问冲突问题。每个处理器返回结果都在自己的文档子集中，所以也没有“写”冲突。第8章 并行和分布式信息检索物理文档分割则是把文档分割为离散的、自包含的文档子集，每个子集对应一个并行处理器，每个子集有自己的倒排文件。物理倒排表分割后，每个子集合具有自己独立的倒排表结构，因此可以供不同的处理器单独调用，相对比较灵活。但是
22、，由于独立的倒排表没有全局的统计信息(在进行检索时通常需要全局的统计信息来计算文档和查询的匹配相似度)，所以对每个子集进行检索时必须要有另外的处理来获得全局信息。方法通常有两种：一种是采用复制的方法，即将全局信息复制多份分配到每个独立的索引倒排表中；另一种是在每个子集合检索时分两步走，第一步获取全局信息表，第二步才进行检索。前一种方法比较耗费空间，对索引表的更新也比较复杂；后一种方法需要较大的通信开销。第8章 并行和分布式信息检索总的来说，逻辑文档分割方法的通信开销很小，因此总体性能会高于物理文档分割，但是必须要对普通倒排表增加额外的数据结构来进行转换。而物理分割方法的灵活性比较强，每个文档子
23、集可以单独检索。通过物理分割的方法，很容易将非并行的信息检索系统转换为并行的检索系统。使用查询项分割方法时，要将每个关键词项分配到不同处理器上。对于倒排表来说，就是将关键词项表(posting list)进行分割(逻辑的或者物理的)，分别对应到不同的处理器上。在进行查询时，查询项将被分解成多个关键词查询，每个关键词对应不同的处理器分别进行处理。处理结果按照查询的语义进行合并。例如，如果是多个关键词布尔表达式查询，如查询“并行AND 检索”，则合并的主要工作是进行布尔操作。如果是需要对多个子结果进行排序，则合并的主要工作是评分归一化并排序。第8章 并行和分布式信息检索相对而言，数据集分割方法能够
24、提供更简单的倒排表构建和维护。Jeong和Omiecinski通过实验对文档分割方法和查询项分割方法进行了比较9：假设每个处理器有自己的I/O通道和磁盘，当关键词在文档和查询中呈偏态分布(skewed)时，采用数据集分割的方法性能较好；而当关键词在查询中呈均匀(uniform)分布时，查询项分割方法更优越。数据分割后，需要存放到文件系统上供多处理器并发读写。普通的文件系统通常很难满足搜索引擎大规模数据读取的需求。下面介绍Google的并行文件系统GFS。第8章 并行和分布式信息检索2 2 并行文件系统并行文件系统GFSGFS GFS是Google为搜索引擎系统量身定做的文件系统。在Google
25、看来，用于搜索引擎的文件系统必须符合下面的应用需求：文件系统是建立在廉价通用主机平台上的，这些硬件可能经常出问题。为此，文件系统必须能够一直监视自己的状态并从灾难中恢复过来。文件系统存储着许多大文件。数目大概是几百万个，大小为100 MB或者更大，几GB的文件在系统中也是常见的。小的文件也要支持，不过可以不用专门为其作优化处理。需要支持两种类型的读取方式：大规模流读取方式和小规模随机读取方式。在大规模流读取中，一个操作通常会从一个连续的文件区域中读取几百K或者更多的数据。随机读取则可能在任意位置读取几KB的数据。第8章 并行和分布式信息检索写的方式和读的方式也类似。大量的数据通常以追加的方式添
26、加到文件最后，因为这些数据一次写入后通常就不再更改了。随机写入也支持，但不作优化。系统必须能够高效地实现特定的原语，保证多个客户端能并发地对同一个文件进行追加记录。对于搜索引擎的文件系统而言，稳定的高带宽比低延时更重要。大多数应用程序，需要在高传输速率下，大块地操作数据。为此，GFS提供了文件系统常用的接口，比如create、delete、open、close、read、write。同时，还特别地增加了两个原语：snapshot和 record append。snapshot操作以最低开销拷贝一个文件和目录。record append操作让多个客户端并发地给同一个文件追加记录。第8章 并行和分
27、布式信息检索GFS可建立在通用主机组成的集群系统上，包括一个主节点(GFS master)，多个块服务器(chunk server)节点和客户端(GFS client)，如图8-6所示。节点运行Linux操作系统，在一台机器上可同时部署块服务器和客户端。第8章 并行和分布式信息检索图8-6 GFS 架构3第8章 并行和分布式信息检索在GFS中，文件被分成固定大小的块(chunk)，块的大小是固定的64 MB。块创建的时候主节点会为其指定一个全局唯一的64位的句柄(chunk handle)，并以Linux文件的形式保存在块服务器的本地磁盘上。利用句柄和字节范围对块进行读写访问。为了提高可靠性，
28、块在其他块服务器上会有副本，通常有3个副本，用户也可以根据需要指定副本数目。主节点管理文件系统的所有元数据信息，包括命名空间、访问控制、文件到块的映射表、块的位置等。它同时控制文件系统的全局性操作，管理整个系统的所有块副本，决定块的位置，创建新块和相应的副本，协调多变的系统活动以保持块被完全复制，均衡所有块服务器之间的负载，回收没有使用的存储空间。主节点会定时通过心跳信息与块服务器进行交互，发送指令同时收集块服务器的状态信息。第8章 并行和分布式信息检索GFS客户端实现文件系统API，与主节点和块服务器进行交互，进行读写操作。应用程序利用GFS Client就可以访问文件系统。客户端从主节点获
29、取元数据信息后，就直接与块服务器交互，从块服务器获取数据。下面对照图8-6，说明GFS的各个模块之间是如何交互完成一个读操作的。第8章 并行和分布式信息检索GFS中执行一个简单的读数据操作的工作流程如下：客户端可以把数据的偏移位置(offset)转换为块内索引号(chunk index)，并和文件名(filename)一起发送到主节点，主节点把请求块的句柄和块的位置(chunk location)发回到客户端；客户端接着从多个副本中选择一个，通常选择离自己最近的块服务器，把句柄、偏移位置和读取字节长度发送过去；之后，数据的传送在客户端与块服务器之间进行，不再需要主节点的参与，如图8-6黑色的数
30、据线所示。一般数据访问存在空间局部性，以后如果该客户端需要访问同一块服务器中的数据，不再向主节点发送请求，而是直接向块服务器发送数据读取请求。GFS采用一个松散的一致性模型，不仅能很好地支持分布式应用，而且实现起来也方便、高效。第8章 并行和分布式信息检索8.2 8.2 分布式信息检索分布式信息检索 与并行检索系统不同，一个分布式信息检索系统(Distributed Information Retrieval，DIR)由多个信息资源服务器(Collection Servers)和一个或多个代理服务器(Broker)两部分组成。用户向代理服务器提交查询，代理服务器将会用这个查询检索信息资源服务器
31、的子集完成所需信息的查找。子集中的每个信息库服务器反馈给代理服务器一个按相关度由大到小排列的信息列表。最后，代理服务器对所有的结果列表进行整合，形成新的信息列表反馈给用户。分布式检索系统的体系结构由下面几个部分构成，如图8-7所示。相对于集中式信息检索系统，分布式信息检索系统的构建和工作流程模式有很大的不同：第8章 并行和分布式信息检索图8-7 分布式检索系统的体系架构第8章 并行和分布式信息检索(1)资源选择(Collection Resource)：获取一个资源的内容描述(Collection Description)，根据资源内容描述符和查询的比较，决定最可能包含所需信息的资源，对每一个
32、查询可能都要执行这个操作；(2)文档选择：对选择的目标资源进行检索，并选择相关文档；(3)信息融合：把来自不同资源的相关文档合并为结果列表，并输出给用户。归纳而言，分布式信息检索系统需要解决资源选择、文档选择和信息融合三大问题，下节以元搜索引擎为例进行说明。第8章 并行和分布式信息检索8.3 8.3 元搜索引擎元搜索引擎元搜索引擎是分布式信息检索的典型应用。元搜索引擎被称为搜索引擎之上的搜索引擎，它自己并不收集网站或网页信息，通常也没有自己的资源库和网络爬虫。元搜索引擎通过调用其他独立搜索引擎来完成搜索功能。用户在元搜索引擎的用户界面提交查询，然后元搜索引擎把这一查询请求发送给许多独立的搜索引
33、擎。由于不同的搜索引擎可能会有不同的接受命令的格式，所以，用户查询请求应该先转换成其他搜索引擎能够接受的命令格式。然后元搜索引擎把从每个独立搜索引擎返回的结果合并成一个单一的排序列表，并返回给用户。元搜索引擎原理如图8-8所示。第8章 并行和分布式信息检索图8-8 元搜索引擎原理图第8章 并行和分布式信息检索从元搜索引擎的结构中，元搜索引擎的技术重点在于查询前的处理(检索请求提交机制和检索接口代理)和结果的集成。元搜索引擎可以灵活地选择所要采用的独立搜索引擎。它一般都是选择那些比较典型的、性能优异的独立搜索引擎。这种强强联合的结果保证了搜索结果的权威性和可靠性。它还可以充分发挥各个独立搜索引擎
34、在某个搜索领域的功能，弥补独立搜索引擎信息覆盖面的局限性。总的来说，元搜索引擎与独立搜索引擎相比，具有如下主要优点：第8章 并行和分布式信息检索(1)信息的覆盖面。元搜索引擎一般都要默认调用它自己认为比较好的若干个普通搜索引擎，而且大多数元搜索引擎都提供给用户在一定范围内选择搜索引擎的功能。有些元搜索引擎还以频道的方式为用户提供专业搜索引擎的分类。这样，用户可以根据自己的喜好和要查询的内容选择相应的搜索引擎。(2)搜索结果的权威性和可靠性。在独立搜索引擎中，索引数据库的更新需要一定的周期，而且搜集的信息也各有一定的侧重，元搜索引擎调用多个独立搜索引擎获取搜索结果，这种方式首先保证了信息的互补性
35、，其次与独立搜索引擎相比，提高了信息的新鲜度。如果同样的搜索结果在多个独立搜索引擎中同时出现，那么说明这个搜索结果比较重要。这样就避免了一些独立搜索引擎人工干预搜索排名的缺点，使得搜索结果的排序更加公正。有些元搜索引擎还检查搜索结果链接的存在性，这样可以保证用户得到的元搜索结果的可靠性。第8章 并行和分布式信息检索(3)易维护性。所谓易维护性，是针对元搜索引擎的管理者而言的。元搜索引擎省却了独立搜索引擎中收集和存储网页、建立和存储索引的工作。它将自己所调用的搜索引擎看成一个可以独立完成一定功能的实体，不需要去维护它们，只需知道它们的调用接口即可。元搜索引擎的查询精度在很大程度上依赖于它所调用的
36、搜索引擎的查询精度，所以在设计元搜索引擎时可以把主要精力放在搜索引擎的选择、查询请求的优化和搜索结果的优化等方面。一般的元搜索引擎都提供了对应的优化机制。元搜索引擎的核心问题是解决如何调用其他搜索引擎的索引数据库，如何获取查询词在其他搜索引擎中的查询结果以及如何评价、排序、呈现结果等，解决这些问题的主要技术有用户查询转换、检索机制设计与优化、检索结果输出、分布式数据库调用等技术。第8章 并行和分布式信息检索1.1.用户查询转换用户查询转换元搜索引擎定制查询界面供用户输入查询词，需要根据不同的搜索引擎转换成可以进行检索的查询表达式，不同的搜索引擎有不同的检索语法和操作符使用技巧，需要对提问进行处
37、理。同时要对搜索引擎不能处理的检索方式进行排除，并选择一种合适的方式来匹配。第8章 并行和分布式信息检索2.2.检索机制设计与优化检索机制设计与优化对于搜索引擎初始化方式、各个搜索引擎结果平衡处理等问题，都需要在检索机制的设计初期进行规划，这主要受到检索反馈速度、检索结果满意度等因素的影响，目前，搜索引擎初始化主要有用户参与、系统默认或自动随机处理等方式。检索结果的处理需要考虑如何衡量不同搜索引擎结果之间的相关程度。简单的处理方式是以搜索引擎为单位，在选定的独立搜索引擎下面显示比较靠前的结果；复杂的处理方式是以记录为单位，通过判定某一记录在多个独立搜索引擎中被评价的指数，如果多个独立搜索引擎都
38、检出该结果，那么该记录将被排列在整个显示的前面，同时后面标注出是在哪些搜索引擎中检出的。第8章 并行和分布式信息检索3.3.检索结果输出检索结果输出结果输出处理一般有两种形式：直接引用原始结果页面技术与结果页面定制技术。直接引用原始结果页面是元搜索技术中较为简单易行的方式，在自制的页面中将表单提交的对象修改为独立搜索引擎调用的脚本文件。在这种情况中，一般无需进行结果去重，只需完成表单提交的转换即可。结果页面定制技术则要对结果进行更多的加工处理，主要包括：去重和遴选处理，选择相关程度高的记录并加以显示，同时删除可能被多个独立搜索引擎同时检出的记录；结果的再度排序，元搜索引擎并不是完全选取在独立搜
39、索引擎中得到的结果的前几条记录，而是需要再度排序，根据检索机制对相关度判断的标准来比较各个搜索引擎得到的结果。第8章 并行和分布式信息检索4.4.分布式数据库调用技术分布式数据库调用技术直接调用独立搜索引擎结果页面的元搜索引擎不需与独立搜索引擎的索引数据库直接交换数据，只需直接引用独立搜索引擎的结果页面；而查询多个搜索引擎的元搜索引擎则需在满足独立搜索引擎的数据库访问权限的情况下，实现对其索引数据库的访问和二次开发。各独立搜索引擎的数据库分布在不同的地域，要实现对异地、异构数据库的访问，需要使用一系列诸如分布计算等相关的核心技术。同时，不同数据库调用结果响应时间长短不一，这也会直接影响到结果页
40、面的呈现。第8章 并行和分布式信息检索8.3.1 8.3.1 系统架构系统架构 元搜索引擎的参考软件组成结构如图8-9所示。下面讨论每个软件组成的功能和它们之间的相互作用。图8-9 元搜索引擎系统架构图第8章 并行和分布式信息检索1 1 资源选择资源选择 如果元搜索引擎中的成员搜索引擎(Component Search Engines)的数目较少，就把用户的查询请求发送给每个成员搜索引擎。但是，当成员搜索引擎的数量很大时，把查询请求发送给每个成员搜索引擎是不可能的，这是因为在这种情况下，对于这个查询请求，本地数据的很大部分都是没有用的。例如，假设用户只对查询的10个最匹配的文档感兴趣，很明显，
41、那10个想要的文档最多在10个成员搜索引擎的索引库中。因此，对于这个查询请求来讲，如果搜索引擎的数量远远超过10个，那么将会有很大部分的成员搜索引擎没有用。发送查询请求到没有用的成员搜索引擎会出现一些问题。首先，分派查询请求到没有用的成员搜索引擎消耗元搜索引擎站点的资源。第8章 并行和分布式信息检索第二，从元搜索引擎传输查询请求到没有用的成员搜索引擎，和从这些搜索引擎向元搜索引擎传送没有用的文档都将带来不必要的网络流量。第三，评估一个无用索引库的查询请求将会浪费本地系统的资源。第四，如果从无用的成员搜索引擎返回大量的文档，元搜索引擎就要花费大量的精力来识别哪些是有用的文档。因此，发送每个用户的
42、查询请求到潜在有用的搜索引擎是很重要的。对于一个已知的查询请求，搜索潜在有用的搜索引擎的问题就是资源选择问题。资源选择器就是负责对于每个用户的查询请求，识别出潜在有用的成员搜索引擎。一个好的资源选择器应该能够识别出尽可能多的潜在有用成员搜索引擎，同时能够使无用成员搜索引擎当作潜在有用成员搜索引擎的可能性最小化。第8章 并行和分布式信息检索当一个元搜索引擎从用户接收到一个查询时，它就会调用资源选择器来选择元搜索引擎的成员搜索引擎，并将查询发向这些成员搜索引擎。一个好的资源选择算法应该能准确地找到潜在有用的成员搜索引擎，目前已经有很多方法来实现资源选择问题(相关算法详见8.3.2节)，这些方法的区
43、别都体现在如下一些方面：资源的表示、根据有关查询选择资源有用信息的方法、资源选择有用性的评价等。第8章 并行和分布式信息检索2 2 文档选择文档选择对于每个资源选择器选择的搜索引擎，文档选择器决定从搜索引擎的索引库中返回什么文档。目的是从搜索引擎中返回尽可能多的潜在有用的文档，同时最小化返回无用的文档数。如果从一个搜索引擎中返回很多无用的文档，元搜索引擎就得花很大的精力来区分哪些是潜在的有用文档。第8章 并行和分布式信息检索一个最简单的方法是让每个资源服务器都将相似的文档返回给用户，但是这样会导致太多的文档返回，增加了通信的开销和存储空间，同时也增加了结果融合的难度。如前面所讨论的，资源服务器
44、通常的做法都是将检索到的文档按相似度降序排列。因而，文档选择可以分解为下面两个问题：(1)设置从资源库返回的检索文档数，如果从资源库中返回k个文档，那么将选择相似度最大的k个文档；(2)为资源库设定一个门限，使得只有相似度大于这个门限的资源库中的文档才会被返回给用户。第8章 并行和分布式信息检索3 3 查询分发查询分发查询分发负责和被选定的搜索引擎服务器间建立连接，并负责发送查询请求。这个过程通常使用HTTP协议，每个搜索引擎对于HTTP请求方法(例如，GET方法和POST方法)和查询格式都有它自己的要求。查询分发必须正确满足每个成员搜索引擎的要求。一般情况下，发送给每个特定搜索引擎的查询请求
45、很可能与元搜索引擎收到的查询请求不相同。也就是说，最初的查询请求在发送给成员搜索引擎之前，被翻译成一个新的查询请求。Chang等人提出了查询翻译的一些规则30。第8章 并行和分布式信息检索对于一个向量空间查询，查询翻译通常直接保留用户查询中的所有词语。也有两个例外，第一，在将查询发给成员搜索引擎之前，原始的用户查询的相对词频权重可能会有所调整。通过重复某个查询词到特定的次数，就能改变不同查询词的相对重要性。第二，从一个成员搜索引擎检索到的文档数量可能也和用户想要的有差距。例如，假定一个查询，用户想要m篇文档，文档选择器可能决定要从某个成员搜索引擎中检索到k篇文档。在这个例子中，k就是由翻译查询
46、发给成员搜索引擎的，很明显，k不同于m。第8章 并行和分布式信息检索4 4 结果融合结果融合从被选定的成员搜索引擎的得到结果返回给元搜索引擎，结果融合把这些结果组合成一个单一的排序列表。根据用户的需要，返回列表的前m个文档给用户。一个好的结果融合应该把所有返回的文档按照降序排列。通常，由于不同的数据库可能有不同类型的搜索引擎和不同的文本统计，所以，结果融合的工作是非常困难的。最准确的解决方案是规范化从不同成员搜索引擎检索得到的文档得分，或者使用需要合作的全局文档统计，或者是在搜索客户端重新计算文档得分。第8章 并行和分布式信息检索8.3.2 8.3.2 资源选择资源选择资源选择就是指选择最合适
47、的信息资源的子集，以使这些子集包含与查询相关的信息量最多。资源选择最简单的方法是用户自己选择信息资源库去进行检索，这是目前分布式搜索引擎(如元搜索引擎)常用的方法。但有时用户对信息资源的利用知识有限，所以有的分布式信息检索中要求检索系统对用户的查询能够自动地选择信息资源，并且保证这些信息资源中包含与用户查询相关的检索内容最多。同时，如果将查询在每个信息资源库中进行检索，检索的完整性效果自然是最好的，但是这样做的成本很高，而且还会造成检索响应时间过长，增加用户的负担，因而对信息资源库进行选择的目标是尽可能降低信息库子集的数量，尽量保证检索的效率。第8章 并行和分布式信息检索给定一个需求信息和一组
48、资源描述集，系统是怎样选择检索的资源呢？资源选择的等价问题是根据满足信息需求的条件来对资源进行有效的排序，以便用户能根据排序的结果进行有针对性的选择，这涉及到资源排序的算法问题。Meng和Yu等人将这些方法归类为以下三种10：概略表示方法(Rough Representation Approaches)，统计表示方法(Statistical Representation Approaches)和基于学习的表示方法(Learning-based Approaches)。这些方法的性能评估可参见文献27。第8章 并行和分布式信息检索1 1 概略表示方法概略表示方法概略表示方法用一些关键词和短语来表
49、示本地资源，但该方法对于资源的组成只提供了一般的解决措施，因而概略表示方法对于资源的选择是不精确的，该方法一般通过手动产生。每个资源都要人为手动地设置一两个单词作为主题词或分类关键词。用户查询只有和关键词匹配，才能决定哪个资源是最适合用户需要的。匹配可能是针对一个或多个领域，如主题、描述等，这些可由用户选择。资源的排列也是依照查询的匹配程度来进行的，这样用户就可以从结果列表中及时选出所要的信息资源库。第8章 并行和分布式信息检索资源的文本描述转化为一种结构性的表示。这种转换可以手动执行，WordNet11就可以应用在消除主题词(topical words)歧义的转化过程中。【例例8-28-2】
50、在文档World Factbook中，语句“World facts listed by country”可以转化为如下的结构表示：Topic：country Synset：nation，nationality，land，country，a_people Synset：state，nation，country，land，commonwealth，res_politic Synset：country，state，land，nationInfo-type：facts第8章 并行和分布式信息检索在WordNet中，每个词有1个或多个同义词集，主题词“country”有4个同义词集，其中3个是相关的，所
