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

18.并行和分布式信息检索ParallelandDistributedIR并行信息检索ParallelIR分布式信息检索DistributedIR2并行IR提纲简介回顾并行计算和并行程序性能的度量介绍在MIMD并行体系结构下实现倒排文件的基本方法结论3简介一方面，网络上地理位置分散的异构数字化信息的规模越来越大，导致标引和检索开销不断增加，检索响应时间越来越长。The另一方面，尽管计算机软硬件技术发展迅速，但是对于大规模信息来说，单个CPU、单台计算机的处理能力仍然相对非常有限。因此，需要引入多个CPU、多台计算机进行“团队作战”--分布式并行计算！4并行计算(ParallelComputing)并行计算：用多个处理器去求解单个问题，把单个大问题分解成若干“部分”，每个“部分”采用单个处理器去解决。按照指令(Instruction)流和数据(Data)流的数目，Flynn将并行体系结构分成四类：SISD：单指令流单数据流，如传统的冯·诺依曼计算机。SIMD：单指令流多数据流，N个处理器，N个数据流，但是多个处理器执行相同的操作。MISD：多指令流单数据流，N个处理器处理共享内存中的单数据流，每个处理器的操作不同，目前MISD结构已经非常少见。MIMD：多指令流多数据流，N个处理器，N个指令流和N个数据流，每个处理器都有自己的控制单元、处理单元和局部内存。多处理器可以处理不同任务或者协同处理单个任务。MIMD是目前最通用和最流行的一类并行体系结构。处理器之间交互(通信)频繁的MIMD系统称为紧耦合系统，反之称为松耦合系统。5并行程序性能度量（一）加速因子SpeedupAmdahl法则：一个既定问题的最大加速率取决于该问题中只能顺序执行的部分所占的比率f，它与加速率之间的关系为其中，N是处理器的数量S最佳顺序执行算法运行时间并行算法运行时间fNffS1/)1(16并行程序性能度量（二）效率指标EfficiencyS是加速因子，N是处理器数量理想情况下，，即没有处理器闲置或进行着不必要的工作；实际中无法达到NS17并行IR算法的实现途径开发新的检索策略，并直接采用并行算法将现有的、研究较多的信息检索算法改造为并行算法8MIMD体系结构MIMD体系结构在如何定义和使用并行来解决问题上提供了很大的灵活性。TherearetwowaysinwhicharetrievalsystemcanexploitaMIMDmachine:Parallelmultitasking并行多任务Partitionedparallelprocessing分割式并行处理9MIMD体系结构：并行多任务并行计算机中每个处理器运行一个分离的、独立的搜索引擎搜索引擎并不协同处理单个查询BrokerUserQueryResultUserQueryResultSearchEngineSearchEngineSearchEngineSearchEngineSearchEngine可提高系统的吞吐量，不能改变单个查询的响应时间简单，但需要对系统的硬件资源进行合理的权衡10MIMD体系结构：分割式并行处理将单个查询的计算划分为多个子任务，并分配给多个处理器执行将信息检索的计算分割归结为如何对数据进行分割中介器整合各处理器返回的查询结果BrokerUserQueryResultSubquery/ResultsSearchProcessSearchProcessSearchProcessSearchProcessSearchProcess11MIMD体系结构：数据分割方法按文档分割（逻辑分割和物理分割）：N个文档分散在P个处理器上并行处理，每个并行进程处理针对N/P个文档的查询按词分割：t个索引项分散在P个处理器上并行处理，每个文档以及查询的处理是分布在多个处理器上的k1k2...ki...ktd1w1,1w2,1...wi,1...wt,1d2w1,2w2,2...wi,2...wt,2.....................djw1,jw2,j...wi,j...wt,j.....................dNw1,Nw2,N...wi,N...wt,NIndexingItemsDocuments检索算法处理的基本数据元素12InvertedFiles:LogicalDocumentPartitioning数据划分从倒排索引数据结构上来说倒排索引与原单进程顺序处理没有区别。倒排索引能够支持并行进程直接访问各进程所管辖的那一部分文档对应的倒排索引部分。13ExtendeddictionaryentryfordocumentpartitioningitemiP1P2P3P4InvertedListTermiDictionaryInvertedFiles:LogicalDocumentPartitioning14查询处理过程调度者broker发起P个并行进程来处理查询；每个进程在自己管辖的文档集上执行相同的文档排名算法；搜索进程在一个共享数组中记录文档排名；最终由调度者产生文档的排名列表。InvertedFiles:LogicalDocumentPartitioning倒排索引构建索引构建之前需要在处理器之间划分好各自所管辖的文档；每个索引进程产生一个倒排索引，按索引项排序；最终的倒排索引需要归并各进程产生的倒排索引。15数据分割方式文档从物理上划分成不同子集，每个子集归属一个进程管辖每个文件子集包含自己的索引查询处理过程调度者broker将查询提交给所有并行搜索进程；每个并行进程处理查询并返回匹配文件列表；调度者收集各个进程返回的匹配文件列表并把它们合并为一个最终的匹配文件列表。倒排索引构建每个处理器并行地针对自己管辖的文档集产生独立的完整索引；需要做归并以统计所有文档的全局信息并把这些信息分发到各文档集的词典中。InvertedFiles:PhysicalDocumentPartitioning16数据分割方式倒排索引按词表集合划分，不同的词表集合对应不同的并行处理器处理查询处理方式查询根据不同词表集被拆解成多个，每个子查询被送往对应的处理器进行处理；处理器产生匹配列表以及排名值并将列表返回给调度者；调度者将不同处理器返回的匹配结果加以混合。InvertedFiles:TermPartitioning17Example文档集：DocumentText1Peaseporridgehot2Peaseporridgecold3Peaseporridgeinthepot4Peaseporridgehot,peaseporridgenotcold5Peaseporridgecold,peaseporridgenothot6Peaseporridgehotinthepot18ExampleInvertedFile6,1coldhotinnotpeaseporridgepotthe1,12,13,14,25,2Dictionary2,14,11,14,15,16,13,16,14,15,16,11,12,13,14,25,23,16,13,16,1InvertedLists5,119ExampleLogicalDocumentPartitioning6,1coldhotinnotpeaseporridgepotP1P2P3the1,12,13,14,25,2InvertedListTerm“pease”Dictionary20ExamplePhysicalDocumentPartitioningcoldhotinnotpeaseporridgepotthe3,14,24,14,13,14,13,14,23,13,1P2hotpeaseporridge1,12,11,11,12,1P1cold2,16,1hotinnotpeaseporridgepotthe5,25,16,16,15,16,15,26,16,1P3cold5,121ExampleTermPartitioning6,1coldhotinnotpeaseporridgepotthe1,12,13,14,25,22,14,11,14,15,16,13,16,14,15,16,11,12,13,14,25,23,16,13,16,1P1P2P35,122小结在大规模文档集进行搜索开销会较大，可以考虑采用并行处理以提高速度讨论了两种基于MIMD体系结构的并行处理方式按文档分割Documentpartitioning按词分割Termpartitioning文档分割在倒排表构建和维护上较为简单如果Term在查询和文档中的分布比较偏斜(skewed，扭曲，不对称)时，则文档分割方法较好如果Term在Query中均匀分布，则Term分割方法较好23为什么要分布式信息检索DistributedIR?通过多处理器分割处理大型数据集提高处理速度由于政治的或管理上的需求，不同数据集分布在不同的地方比如学校图书馆里有很多电子资源，不同的电子资源需要远程访问不同的服务器Internet上一些专业数据库不是面向公众开放的，需要用户名/密码网上的数据集/库可能很多Web上有各种各样被索引的集合24分布式信息检索DistributedIRIR经常被看成是搜索一个单独的文档集合集合有哪些?单独的源的集合,e.g.,WallStreetJournal?(Whattimeperiod?)单独的位置的信息集合,e.g.,theUMassPhysicalSciencesLibrary?图书馆的集合,e.g.,allUMassAmherstlibraries?分布式信息获取：搜索多于一个集合本地环境,e.g.,alargecollectionispartitioned广域网环境,e.g.,corporatenetwork,Internet25并行系统与分布式系统比较分布式系统主要由一组服务进程构成，每个进程运行在独立的处理节点上，委托中介器进程负责接收客户查询，然后将查询分发给服务器，并收集各个服务器返回的中间结果，最后将这些中间结果组合起来，形成最终结果返回给用户。分布式系统在不同计算机上运行的子任务之间的通信是通过诸如TCP/IP之类的网络协议来实现的；而并行系统采用的是基于共享内存的进程通信机制。分布式系统常常通过程序选取一定量的服务器来处理一个既定的查询；而并行系统则是将每个查询都发送给系统中的每个服务器。适于进行分布式计算的应用：可把计算和数据分割为粗颗粒操作，而操作之间只需要较少的通信。例如：基于文献分割的并行信息检索。26分布式IR的主要问题站点描述主要内容，提供哪些服务等等信息源（集合）选择决定搜索哪些集合相对于一个查询来评价不同的集合从排序的集合列表中选择最好的子集结果归并：将不同文档集中搜得的匹配文档归并到一个结果中不同文档集底层统计数据不一致不同的搜索引擎输出信息不一样度量结果的有效性、一致性、人工参与程度等27集合选择的主要方法对于站点数较少或局域网环境选所有集合人工分组选择基于规则的集合选择相关文档分布Relevantdocumentdistribution(RDD)查询探测QueryProbing对于站点较多，WAN或