分布式WEB信息检索技术研究.ppt
《分布式WEB信息检索技术研究.ppt》由会员分享,可在线阅读,更多相关《分布式WEB信息检索技术研究.ppt(67页珍藏版)》请在沃文网上搜索。
1、分布式分布式WEB信息检索技术研究信息检索技术研究Research on Distributed WEB Information Retrieval 博士生:张刚导师:李国杰院士2005年12月Outlinel研究背景l学位论文研究情况和已完成的研究内容l已取得的阶段性成果l下一步的工作计划l科研项目的完成情况l学术论文发表情况l课程完成情况研究背景研究背景l海量信息检索的挑战WEB信息的增长:6个月翻一番表层页面(surface WEB)80亿-100亿Hobbes Internet Timeline统计,截止到2005年8月,互联网上WEB服务主机数已达到70,392,567台 l矛盾与问
2、题80亿 VS.Top10问题!是否80亿个页面都需要查询?如何减少查询量?研究背景研究背景l分布式信息检索是海量信息检索的有效方案团队作战分而治之l分布式信息检索的主要过程文档集合划分集合选择单文档集合检索结果合并分布式信息检索的体系结构分布式信息检索的体系结构分布式信息检索的过程分布式信息检索的过程集合选择查询学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合
3、选择算法语言模型检索 OKAP模型分布式信息检索检索的划分问题建模分布式信息检索检索的划分问题建模l文档集合划分的问题描述 l文档集合的划分模型l模型的解空间分析l文档划分问题最优解的快速解法l算法复杂度分析文档集合划分的问题描述文档集合划分的问题描述l文档集合划分问题问题1:文档分布问题。即:每个子集合中应包含哪些文档问题2:文档集划分个数问题。即:一个给定的文档集合应该被划分成几个子集合l直观的划分原则同一个查询的相关文档,尽可能集中在少数的子集合各个子集合的规模相差尽可能小l影响文档划分的三个主要因素文档集D、查询集Q、查询的相关文档集R文档集合划分的问题描述(文档集合划分的问题描述()
4、l文档集合划分的核心难题文档与查询的相关关系是一种多对多的关系一个查有多个相关文档、一个文档是多个查询的相关文档DocQuery多对多DocQuery多对一问题文档文档集合的划分模型文档集合的划分模型l文档集划分问题1(文档分布问题)建模描述:如果给定一个文档集合D,查询集合Q及其相关文档集R,要将文档集D划分成K个子集合,那么D中的文档如何在各个子集合中分布是最合理的方式什么是最合理的方式?l模型优化原则:求解一种文档集合的划分,使得处理Q中的查询,所需要检索的平均文档数最少l分布式检索的过程第一步:找出含有相关文档的子集合第二步:对于每个子集合,找出其中的相关文档文档集合的划分模型文档集合
5、的划分模型l文档集合划分模型1子集合查询集合相关文档集l模型物理意义查询平均文档数文档的划分结果就是当avgdoc1取最小值时对应的一组Si举例举例l集合D=1,5,6,7,8,9,12共7元素,另外知道四个查询的相关文档集合R1=1,5,9,12R2=1,5,7,8R3=5,6,7,9R4=7,8,9,12l7个数被划分成三个子集合S1=1,5,6,S2=7,8,S3=9,12l模型代价为(|S1|+|S3|)+(|S1|+|S2|)+(|S1|+|S2|+|S3|)+(|S2|+|S3|)/4文档集合的划分模型文档集合的划分模型l文档划分问题2(文档集划分个数问题)建模问题描述:如果给定一
6、个文档集合D,查询集合Q及其相关文档集R,在不考虑机器等资源限制条件下,应该划分成多少个子集合是最合理的l重温分布式信息检索过程第一步:找出含有相关文档的子集合第二步:对于每个子集合,找出其中的相关文档文档集合的划分模型文档集合的划分模型l文档集合划分模型2考虑文档集合划分个数情况下的,平均查询文档数查询集子集合相关文档集子集合个数文档的划分结果就是当avgdoc2取最小值时,对应的 一组Si和K文档集合的划分模型文档集合的划分模型l模型2的两种极端情况传统集中式检索,无文档划分每个文档作为一个文档集合两种情况按照模型是一致的,实际上也没有差别可行解空间分析可行解空间分析l模型1可行解空间分析
7、有m个小球放入n个盒子中(m=n),小球有差别,盒子没有差别,不准有空盒,所有的可能性中寻求一个最佳的放法(组合个数为第二类Stirling数)l模型2可行解空间分析有m个小球放入n个盒子中(m=n),小球有差别,盒子没有差别,允许有空盒,所有的可能性中寻求一个最佳的放法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l模型1与模型2的关系l关键问题:求解模型1的最优解类哈夫曼编码的最优解求解算法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l模型1最优解求解过程随子集合个数减少,模型1的最优解分为两个阶段解法第一阶段:模型1的最优解是一个常数第二阶段:模型1最优解的构造采用
8、类哈夫曼编码算法文档划分问题最优解的快速解法文档划分问题最优解的快速解法l第一阶段模型1的最优解为常数首先考虑每个文档是一个子集合的情况,此时模型1的最优解为如果将子集合个数减少,需要将部分子集合合并,合并原则是:合并后新的子集合中的文档都是同一个查询的相关文档,这种过程不断进行,直到无法进行为止当合并无法进行时,是模型的一个分界点,在此之前模型1的最优解保持不变文档划分问题最优解的快速解法文档划分问题最优解的快速解法l第二阶段模型1的最优解算法当过了上述临界点,再进行合并时,就会出现一个子集合中包含多个查询的相关文档的情况此时该子集合在计算模型1的最优值是就会被多次使用,使用的次数为不同查询
9、的个数因此决定哪两个子集合合并时,需要找出一种合并以后代价最小的方案求解最小代价的方法,类似于哈夫曼编码的过程文档划分问题最优解的快速解法文档划分问题最优解的快速解法l类哈夫曼编码算法模型1与哈夫曼编码的类比l子集合Si为待编码的字符l子集合的模|Si|为该字符的编码长度 l子集合在计算模型1被使用的次数,为字符的出现频率由此模型1的求解过程就是完成对子集合Si的一个编码过程,也就是构建一个哈夫曼编码树文档划分问题最优解的快速解法文档划分问题最优解的快速解法l演示代价8代价6代价6代价4模型求解临界点算法复杂度分析算法复杂度分析l第一次比较合并需要两两比较代价计算次数为l此后采用动态规划算法,
10、利用前次计算的结果1 2 3 4 51 2 3 4 51 2 34 51 2 34 5算法复杂度分析算法复杂度分析l模型1算法时间复杂度l模型2算法时间复杂度l空间开销文档集合划分模型试验分析文档集合划分模型试验分析l文档集描述TREC2002、2003、2004年的查询集合,共324个 相关集合中文档个数为3853个不同文档个数为3778篇69篇文档同时是2个查询的相关文档3篇文档同时是3个查询的相关文档 文档集合划分模型试验分析文档集合划分模型试验分析l模型最优值随子集合个数变化曲线横轴:子集合个数纵轴:最优值对数l最优划分方案子集合个数为52划分方案为模型1对应的模型参数Si文档集合划分
11、模型实验分析文档集合划分模型实验分析l最优划分方法与其他划分方法比较模型2最优划分基于内容相关聚类划分随机划分最优划分 内容聚类 随机划分 avgdoc150.04 273.59 653.15avgdoc2102.04 325.59 601.15 文档集合划分模型实验深入分析文档集合划分模型实验深入分析l划分模型的假设及实践应用中的方法知道全部查询和查询相关文档为前提实践中,可以利用查询日志,得到查询以及查询的相关文档,甚至可以利用查询出现的次数进行优化l模型综合考虑了直观划分的两个指标相关文档集中分布子集合规模差距尽量小文档集合划分模型小结文档集合划分模型小结l给出了一个可以量化的最优划分模
12、型给出了一种划分的最优化标准回答了集合划分的两个问题可行的模型最优化解法l对其他研究领域的意义数据流管理平台l扫描关键词类似文档l关键词的分布类似文档集合的划分数据库管理系统l数据的分布问题学位论文研究情况和已完成的研究内容学位论文研究情况和已完成的研究内容l分布式WEB信息检索的集合划分问题分布式信息检索检索的划分问题建模 基于内容的文档划分技术基于链接的文档划分算法分布式信息检索文档集合划分算法评价l分布式信息检索的集合选择问题研究 tf.idf系列模型CORI集合选择算法语言模型检索 OKAP模型基于内容的文档划分技术基于内容的文档划分技术l基于内容相关的文档划分思想考虑一个查询的相关文
13、档之间的关系假设:一个查询的相关文档他们在内容上也是相关的l基于内容的文档划分算法策略文档内容相关度的度量基于内容相关度的聚类技术采用快速的聚类算法基于内容的文档划分技术基于内容的文档划分技术l内容相关度度量方法向量空间模型VSM余弦相似度计算l快速聚类方法K-Means聚类技术基于内容的文档划分实验基于内容的文档划分实验l测试集为TREC标注测试集55万文档内容聚类随机平均正确率 0.1161 0.0830 相关的文档数 1172 773 基于内容的文档划分局限基于内容的文档划分局限l效率问题55万文档划分用时大于7天,2颗P4CPU、4GMem125万文档,几乎无法计算出结果l效率问题成因
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
10 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 分布式 WEB 信息 检索 技术研究
