分布式WEB信息检索技术研究Research on Distributed WEB ....ppt

分布式WEB信息检索技术研究Research on Distributed WEB Information Retrieval 博士生：张刚 导师：李国杰院士 Outline 研究背景 学位论文研究情况和已完成的研究内容 已取得的阶段性成果 下一步的工作计划 科研项目的完成情况 学术论文发表情况 课程完成情况 研究背景 海量信息检索的挑战 WEB信息的增长：6个月翻一番 表层页面（surface WEB）80亿-100亿 Hobbes‘ Internet Timeline统计，截止到2005年8月，互联网上WEB服务主机数已达到70,392,567台 矛盾与问题 80亿 VS. Top10问题！ 是否80亿个页面都需要查询？ 如何减少查询量？ 研究背景 分布式信息检索是海量信息检索的有效方案 团队作战 分而治之 分布式信息检索的主要过程 文档集合划分 集合选择 单文档集合检索 结果合并 分布式信息检索的体系结构 分布式信息检索的过程 学位论文研究情况和已完成的研究内容 分布式WEB信息检索的集合划分问题 分布式信息检索检索的划分问题建模 基于内容的文档划分技术 基于链接的文档划分算法 分布式信息检索文档集合划分算法评价 分布式信息检索的集合选择问题研究 tf.idf系列模型 CORI集合选择算法 语言模型检索 OKAP模型 分布式信息检索检索的划分问题建模 文档集合划分的问题描述 文档集合的划分模型 模型的解空间分析 文档划分问题最优解的快速解法 算法复杂度分析 文档集合划分的问题描述 文档集合划分问题 问题1：文档分布问题。即：每个子集合中应包含哪些文档 问题2：文档集划分个数问题。即：一个给定的文档集合应该被划分成几个子集合 直观的划分原则 同一个查询的相关文档，尽可能集中在少数的子集合 各个子集合的规模相差尽可能小 影响文档划分的三个主要因素 文档集D、查询集Q、查询的相关文档集R 文档集合划分的问题描述（Ⅱ） 文档集合划分的核心难题 文档与查询的相关关系是一种多对多的关系 一个查有多个相关文档、一个文档是多个查询的相关文档 文档集合的划分模型 文档集划分问题1（文档分布问题）建模 描述：如果给定一个文档集合D，查询集合Q及其相关文档集R，要将文档集D划分成K个子集合，那么D中的文档如何在各个子集合中分布是最合理的方式 什么是最合理的方式？ 模型优化原则：求解一种文档集合的划分，使得处理Q中的查询，所需要检索的平均文档数最少 分布式检索的过程 第一步：找出含有相关文档的子集合 第二步：对于每个子集合，找出其中的相关文档 文档集合的划分模型 文档集合划分模型1 举例 集合D={1,5,6,7,8,9,12}共7元素，另外知道四个查询的相关文档集合 R1={1，5，9，12} R2={1，5，7，8} R3={5，6，7，9} R4={7，8，9，12} 7个数被划分成三个子集合 S1={1，5，6}，S2={7,8}，S3={9,12} 模型代价为((|S1|+|S3|)+(|S1|+|S2|)+(|S1|+|S2|+|S3|)+(|S2|+|S3|))/4 文档集合的划分模型 文档划分问题2（文档集划分个数问题）建模 问题描述：如果给定一个文档集合D，查询集合Q及其相关文档集R，在不考虑机器等资源限制条件下，应该划分成多少个子集合是最合理的 重温分布式信息检索过程 第一步：找出含有相关文档的子集合 第二步：对于每个子集合，找出其中的相关文档 文档集合的划分模型 文档集合划分模型2 考虑文档集合划分个数情况下的，平均查询文档数 文档集合的划分模型 模型2的两种极端情况 传统集中式检索，无文档划分 每个文档作为一个文档集合 两种情况按照模型是一致的，实际上也没有差别 可行解空间分析 模型1可行解空间分析 有m个小球放入n个盒子中(m=n)，小球有差别，盒子没有差别，不准有空盒，所有的可能性中寻求一个最佳的放法（组合个数为第二类Stirling数） 模型2可行解空间分析 有m个小球放入n个盒子中（m=n），小球有差别，盒子没有差别，允许有空盒，所有的可能性中寻求一个最佳的放法 文档划分问题最优解的快速解法 模型1与模型2的关系 关键问题：求解模型1的最优解 类哈夫曼编码的最优解求解算法 文档划分问题最优解的快速解法 模型1最优解求解过程 随子集合个数减少，模型1的最优解分为两个阶段解法 第一阶段：模型1的最优解是一个常数 第二阶段：模型1最优解的构造采用类哈夫曼编码算法 文档划分问题最优解的快速解法 第一阶段模型1的最优解为常数 首先考虑每个文档是一个子集合的情况，此时模型1的最优解为 如果将子集合个数减少，需要将部分子集合合并，合并原则是：合并后新的子集合