并行和分布式信息获取Parallel and Distributed

1、1,8.并行和分布式信息检索Parallel and Distributed IR,并行信息检索 Parallel IR 分布式信息检索 Distributed IR,2,并行IR提纲,简介 回顾并行计算和并行程序性能的度量 介绍在MIMD并行体系结构下实现倒排文件的基本方法 结论,3,简介,一方面，网络上地理位置分散的异构数字化信息的规模越来越大，导致标引和检索开销不断增加，检索响应时间越来越长。 The WWW contains over 20 billions pages of text, comprising nearly 100 terabytes of data 另一方面，尽管计算

2、机软硬件技术发展迅速，但是对于大规模信息来说，单个CPU、单台计算机的处理能力仍然相对非常有限。 因此，需要引入多个CPU、多台计算机进行“团队作战”-分布式并行计算！,4,并行计算(Parallel Computing),并行计算：用多个处理器去求解单个问题，把单个大问题分解成若干“部分”，每个“部分”采用单个处理器去解决。 按照指令(Instruction)流和数据(Data)流的数目，Flynn将并行体系结构分成四类： SISD：单指令流单数据流，如传统的冯诺依曼计算机。 SIMD：单指令流多数据流，N个处理器，N个数据流，但是多个处理器执行相同的操作。 MISD：多指令流单数据流，N个

3、处理器处理共享内存中的单数据流，每个处理器的操作不同，目前MISD结构已经非常少见。 MIMD：多指令流多数据流，N个处理器，N个指令流和N个数据流，每个处理器都有自己的控制单元、处理单元和局部内存。多处理器可以处理不同任务或者协同处理单个任务。MIMD是目前最通用和最流行的一类并行体系结构。处理器之间交互(通信)频繁的MIMD系统称为紧耦合系统，反之称为松耦合系统。,5,并行程序性能度量（一）,加速因子Speedup Amdahl 法则：一个既定问题的最大加速率取决于该问题中只能顺序执行的部分所占的比率f，它与加速率之间的关系为 其中，N是处理器的数量,最佳顺序执行算法运行时间 并行算法运行

4、时间,6,并行程序性能度量（二）,效率指标Efficiency S是加速因子，N是处理器数量 理想情况下， ，即没有处理器闲置或进行着不必要的工作；实际中无法达到,7,并行IR算法的实现途径,开发新的检索策略，并直接采用并行算法 将现有的、研究较多的信息检索算法改造为并行算法,8,MIMD 体系结构,MIMD 体系结构在如何定义和使用并行来解决问题上提供了很大的灵活性。 There are two ways in which a retrieval system can exploit a MIMD machine: Parallel multitasking 并行多任务 Partitione

5、d parallel processing 分割式并行处理,9,MIMD 体系结构：并行多任务,并行计算机中每个处理器运行一个分离的、独立的搜索引擎 搜索引擎并不协同处理单个查询,可提高系统的吞吐量，不能改变单个查询的响应时间 简单，但需要对系统的硬件资源进行合理的权衡,10,MIMD 体系结构：分割式并行处理,将单个查询的计算划分为多个子任务，并分配给多个处理器执行 将信息检索的计算分割归结为如何对数据进行分割 中介器整合各处理器返回的查询结果,11,MIMD体系结构：数据分割方法,按文档分割（逻辑分割和物理分割）： N个文档分散在P个处理器上并行处理，每个并行进程处理针对N/P个文档的查询

6、 按词分割： t个索引项分散在P个处理器上并行处理，每个文档以及查询的处理是分布在多个处理器上的,检索算法处理的基本数据元素,12,Inverted Files: Logical Document Partitioning,数据划分 从倒排索引数据结构上来说倒排索引与原单进程顺序处理没有区别。 倒排索引能够支持并行进程直接访问各进程所管辖的那一部分文档对应的倒排索引部分。,13,Extended dictionary entry for document partitioning,Inverted Files: Logical Document Partitioning,14,查询处理过程 调

7、度者broker发起P个并行进程来处理查询； 每个进程在自己管辖的文档集上执行相同的文档排名算法； 搜索进程在一个共享数组中记录文档排名； 最终由调度者产生文档的排名列表。,Inverted Files: Logical Document Partitioning,倒排索引构建 索引构建之前需要在处理器之间划分好各自所管辖的文档； 每个索引进程产生一个倒排索引，按索引项排序； 最终的倒排索引需要归并各进程产生的倒排索引。,15,数据分割方式 文档从物理上划分成不同子集，每个子集归属一个进程管辖 每个文件子集包含自己的索引 查询处理过程 调度者broker将查询提交给所有并行搜索进程； 每个并行

8、进程处理查询并返回匹配文件列表； 调度者收集各个进程返回的匹配文件列表并把它们合并为一个最终的匹配文件列表。 倒排索引构建 每个处理器并行地针对自己管辖的文档集产生独立的完整索引； 需要做归并以统计所有文档的全局信息并把这些信息分发到各文档集的词典中。,Inverted Files: Physical Document Partitioning,16,数据分割方式 倒排索引按词表集合划分，不同的词表集合对应不同的并行处理器处理 查询处理方式 查询根据不同词表集被拆解成多个，每个子查询被送往对应的处理器进行处理； 处理器产生匹配列表以及排名值并将列表返回给调度者； 调度者将不同处理器返回的匹配结

9、果加以混合。,Inverted Files: Term Partitioning,17,Example,文档集： Document Text 1 Pease porridge hot 2 Pease porridge cold 3 Pease porridge in the pot 4 Pease porridge hot, pease porridge not cold 5 Pease porridge cold, pease porridge not hot 6 Pease porridge hot in the pot,18,Example,Inverted File,19,Exampl

10、e,Logical Document Partitioning,20,Example,Physical Document Partitioning,21,Example,Term Partitioning,22,小结,在大规模文档集进行搜索开销会较大，可以考虑采用并行处理以提高速度 讨论了两种基于MIMD体系结构的并行处理方式 按文档分割Document partitioning 按词分割Term partitioning 文档分割在倒排表构建和维护上较为简单 如果Term在查询和文档中的分布比较偏斜(skewed，扭曲，不对称)时，则文档分割方法较好 如果Term在Query中均匀分布，则T

11、erm分割方法较好,23,为什么要分布式信息检索Distributed IR?,通过多处理器分割处理大型数据集 提高处理速度 由于政治的或管理上的需求，不同数据集分布在不同的地方 比如学校图书馆里有很多电子资源，不同的电子资源需要远程访问不同的服务器 Internet 上一些专业数据库不是面向公众开放的，需要用户名/密码 网上的数据集/库可能很多 Web上有各种各样被索引的集合,24,分布式信息检索Distributed IR,IR经常被看成是搜索一个单独的文档集合 集合有哪些? 单独的源的集合, e.g., Wall Street Journal? (What time period?) 单

12、独的位置的信息集合, e.g., the UMass Physical Sciences Library? 图书馆的集合, e.g., all UMass Amherst libraries? 分布式信息获取：搜索多于一个集合 本地环境, e.g., a large collection is partitioned 广域网环境, e.g., corporate network, Internet,25,并行系统与分布式系统比较,分布式系统主要由一组服务进程构成，每个进程运行在独立的处理节点上，委托中介器进程负责接收客户查询，然后将查询分发给服务器，并收集各个服务器返回的中间结果，最后将这些中

13、间结果组合起来，形成最终结果返回给用户。 分布式系统在不同计算机上运行的子任务之间的通信是通过诸如TCP/IP之类的网络协议来实现的；而并行系统采用的是基于共享内存的进程通信机制。 分布式系统常常通过程序选取一定量的服务器来处理一个既定的查询；而并行系统则是将每个查询都发送给系统中的每个服务器。 适于进行分布式计算的应用：可把计算和数据分割为粗颗粒操作，而操作之间只需要较少的通信。例如：基于文献分割的并行信息检索。,26,分布式IR的主要问题,站点描述 主要内容，提供哪些服务等等 信息源（集合）选择 决定搜索哪些集合 相对于一个查询来评价不同的集合 从排序的集合列表中选择最好的子集 结果归并：

14、将不同文档集中搜得的匹配文档归并到一个结果中 不同文档集底层统计数据不一致 不同的搜索引擎输出信息不一样 度量 结果的有效性、一致性、人工参与程度等,27,集合选择的主要方法,对于站点数较少或局域网环境 选所有集合 人工分组选择 基于规则的集合选择 相关文档分布Relevant document distribution (RDD) 查询探测Query Probing 对于站点较多，WAN 或Internet 环境 基于内容的集合评价和选择,28,集合选择：选所有集合,能够良好支持布尔模型 结果集是所有搜索结果的并集 能够支持统计模型 归并排序所有集合搜索结果，获取归并后的排名序列 但不同数据

15、集合排名等级并不一致，因为不同集合的统计数据并不一致, e.g., idf, avg_doclen 可以通过在数据集中采用全局参数来计算出可比较的排名顺序 不能扩展到WAN / Internet环境 具备一定的并行处理能力,29,集合选择：人工分组和人工选择,主题接近的集合被组织成集合组 e.g., financial, technology, appellate court decisions 用户选择要搜索哪个组 大多出现在商业搜索服务提供商 e.g., Dialog, West 分组由人手工确定 费时费力，由于不同的人看法可能不一样，分组一致性不好 机器自动判定分组 调度器维持一个中心索

16、引，这个索引是针对集合的。定期针对每个主题查询集合更新索引 自动产生, 具有较好的一致性,30,集合选择：基于规则的选择,每个集合的内容都在知识库中详细描述 few details provided by authors of such systems 基于规则的系统根据不同查询来选择不同的集合 few details provided by authors of how this works CONIT, a research system, never deployed widely Marcus, JASIS 1983 在静态同构的集合上测试过 产生规则很耗时 如果规则改变会产生不一致的

17、选择结果 粗糙分组，对于不常见的需求难以满足,31,集合选择：相关文档分布Relevant Document Distribution (RDD) Voorhees et al, TREC-3, 1994,首先需要生成一个数据库，存储一系列的查询以及在每个集合中对应的查询结果分布情况 当新来一个查询时 在数据库中找到k个最近的查询邻居（相似查询） 在每个集合中将k个查询的分布加以平均，估算出不同集合中查询相关文档的分布情况 根据上述分布情况决定从不同集合各返回多少文档,32,集合选择：相关文档分布Relevant Document Distribution (RDD),假设Q最近的查询是Q1和

18、Q2 如上图所示，Q的RDD估算值为Q1和Q2的平均值 注意：以上方法有效性依赖于Q与Q1,Q2的相似程度,33,集合选择：查询探测Query Probing,向每个集合发送一个轻量级的探测查询probe query 每个集合返回一些统计信息 e.g., collection size, df 客户端将集合排名，选取头n个集合 前提条件 处理轻量级的探测查询要比处理一般查询开销小 e.g., because probe is shorter e.g., because probe does no ranking 客户端基于少数几个词就能够估计集合的内容 轻量级的探测查询占用带宽和时延很少,34,集合选择：对于集合很多的情况,背景 每个集合都搜索的开销太为昂贵 可能有成百上千个集合、集合可能广泛分布在各地、有些集合收费 各集合管理维护是独立的 不能依靠集合自己来描述自己 集合以及查询差异很大 解决方案 搜索数据中心，在数据中心由不同的词代表各个不同的库,35,根据词频来展示一个文档的内容,36,根据词频统计来展示一个集合的内容,37,相关文档计算,对于布尔“与”查询Q估算集合C中可能的相关文档数量： dft = 在集合 C中包含关键词t的文档个数 |C| = 集