第七章 并行和分布式信息检索.ppt

分布式计算(Distributed Computing) 分布式计算 运用网络连接的多台计算机解决一个问题。 分布式信息检索 在分布式环境中，利用分布式计算技术从大量异构的信息资源中检索出对用户有用的信息的过程 分布式环境是指信息资源在物理上分布于各地，但逻辑上是一个整体。 分布式信息检索过程 从用户处接收查询； 把用户查询翻译成检索提问表达式； 确定与提问式相关的数据集； 利用提问式对数据集进行检索； 收集相应的检索结果； 对检索结果进行整理； 将整理结果返回给用户。 分布式信息检索系统体系结构 客户机1 集合选择 结果合并 信息检索 服务器1 客户机2 客户机n 信息检索 服务器2 信息检索 服务器n 网络 网络 文档集合的划分 非合作信息检索 每一个检索服务器由不同组织建立，采用不同的检索模型和方法，每个文档集合的质量未知，合并结果困难。 合作信息检索 每一个检索服务器由同一组织建立，采用相同的检索模型和方法，每个文档集合的质量已知，合并结果相对简单。 随机划分文档集合 语义分割文档集合 文档集合的选择 朴素法 直接将用户的查询请求发送给所有的信息检索服务器进行检索； 粗略法 为每一个信息检索服务器提供描述信息的数据集选择方法； 定性的方法 采用粗略信息代表数据集内容 定量的方法 基于学习的方法 根据查询经验预测数据集对新查询的有用程度 作业 文档集： 1.你\见\或者\不\见\我 2.我\就在\那里 3.不\悲\不\喜 4.你\念\或者\不\念\我 5.情\就在\那里 6.不\来\不\去 要求：假定系统有3个处理器，试画出该文档的倒排文档以及分别按照逻辑文档分割、物理文档分割、语词分割方法下的倒排文档，并比较逻辑文档分割与物理文档分割的异同。若查找包含词项“我”的文档，则在3种分割方法中分别需要那些处理器进行检索？ * * * * * * * * * * * * * * * * * * * * * * * * 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 信息组织、存储与检索 第七章 并行和分布式信息检索 并行信息检索 并行计算(Parallel Computing) 并行计算 将单个问题划分为多个较小的“子”问题，用多个处理器同时分别处理这些“子”问题来得到单个问题的解； 并行计算机 多个可以同时工作的处理器构成的计算机系统； 并行信息检索 把信息检索过程建立在利用并行算法对数据进行分割的基础上； 计算机体系结构分类 按照指令(Instruction)流和数据(Data)流的数目，Flynn将计算机体系结构分成四类： SISD（Single Instruction Single Data ） 单指令流单数据流 SIMD （Single Instruction Multiple Data ） 单指令流多数据流 MISD （ Multiple Instruction Single Data ） 多指令流单数据流 MIMD （ Multiple Instruction Multiple Data ） 多指令流多数据流 MIMD并行体系结构 并行信息检索原理 多个查询之间的并行处理（任务级并行检索） 利用MIMD结构对多个查询的处理并行化，每个处理器处理不同的查询，每个查询的处理之间相互独立，最多只对共享内存中的部分代码或者共有数据实行共享。 并行信息检索原理 单个查询内部的并行处理（进程级并行检索） 将查询的计算量进行分割，分成多个子任务，并分配到多个处理器的有哪些信誉好的足球投注网站进程上去执行。 数据分割方法 检索算法处理的基本数据元素 k1 k2 ... ki ... kt d1 W1,1 W2,1 ... Wi,1 ... Wt,1 d2 W1,2 W2,2 ... Wi,2 ... Wt,2 ... ... ... ... ... ... ... dj W1,j W2,j ... Wi,j ... Wt,j ... ... ... ... ... ... ... dN W1,N W2,N ... Wi,N ... Wt,N 文档 标引词 数据分割方法 文档分割法 对数据矩阵进行水平切割，将文档分割为一系列子任务，每个处理器分别处理一部分文档 语词分割法 对数据矩阵进行垂直分割，每个处理器分别处理一部分标引词 倒排文档的分割 逻辑文档分割（logical document partitioning） 物理文档分割（physical document partitioning） 语词分割（term pa