学位论文 > 优秀研究生学位论文题录展示

搜索引擎中索引剪枝的研究

作　者: 单栋栋
导　师: 李晓明
学　校: 北京大学
专　业: 计算机系统结构
关键词: 倒排索引静态索引剪枝动态索引剪枝 Top K查询处理
分类号: TP391.3
类　型: 博士论文
年　份: 2013年
下　载: 116次
引　用: 0次
阅　读: 论文下载

内容摘要

搜索引擎作为人们获取网络信息的主要入口，正在被越来越多的人使用。不断增长的网页数量和查询请求量使得搜索引擎面临着巨大的性能挑战。通常，搜索引擎每秒需要在数百亿的网页数据上处理成千上万的查询。因此，如何高效地处理查询一直是搜索引擎和信息检索领域中重要的研究问题。本文从索引剪枝的角度出发来研究提升查询处理效率的方法。索引剪枝通常分为静态索引剪枝和动态索引剪枝的方法。静态索引剪枝方法主要用在索引构建阶段。它在索引构建时，去除索引中一些对查询不重要的信息来缩短倒排链长度，减小倒排索引的大小，从而提升查询的速度。动态索引剪枝的方法主要用在查询的处理阶段。它在查询的处理时，通过使用相应的索引辅助结构来跳过一些对查询不重要的文档来提升查询的处理速度。本文分别从静态索引剪枝和动态索引剪枝两方面来研究提升查询处理的方法，并提出了一些新的索引结构和算法来支持高效的查询处理。本文的工作、创新性和主要贡献主要体现在以下几个方面：1.本文提出了一种基本网页结构和重要度的静态索引剪枝方法。在这种剪枝方法中，它一方面利用网页的结构来区别对待在不同结构中信息的重要程度，优先保留重要结构中的信息。另一方面利用网页与网页之间的重要度不同，对重要度高的网页保留更多比例的信息。通过在GOV2数据集上的相关实验，我们发现网页结构和重要度信息对文档的剪枝都有非常大的帮助。结合这两种信息的静态索引剪枝方法在去除80%的倒排项时，P@10指标与使用完整索引的效果相当，存储开销减小了73%，查询处理的速度提升了2倍。2.本文提出了一种基于块最大索引的动态索引剪枝算法的处理框架。在此框架下，本文提出了3个新的动态索引剪枝算法，分别为Block-MaxMaxScore (BMM)， Local Block-Max WAND (LBMW)和Local Block-MaxMaxScore (LBMM)。在这个框架下查询处理主要分为三步：1).选择候选文档。本文提出的算法利用块局部最大分数而不是词的全局最大分数来选择候选文档，大大减少了选择候选文档的数量。2).过滤文档。利用文档所在块最大分数来过滤候选文档。本文提出一种更高效的过滤方法，它能充分的利用查询处理局部性，提升过滤的效率。3).候选文档打分。本文提出的算法利用块最大分数来动态估算文档分数上限，从而可以尽快的结束对不重要的候选文档的打分。实验表明，新提出剪枝算法在查询处理速度上比已有的算法都有明显的提升，它比经典的剪枝方法快近1倍。3.本文提出了两种在块最大索引中存储文档静态分数与词相关性分数的方法。使得动态索引剪枝算法的打分函数在包含文档静态分数时也能对查询进行高效的剪枝。一种方法是对每个块分别存储块中最大的词相关性分数和文档静态分数；另一种方法是先把词相关性分数与文档静态分数合并，然后存储块中最大合并分数。第二种方法相对于第一种方法能更加精确地估算候选文档的分数，但它存在低估候选文档分数的情况。本文分析了产生文档分数低估的原因并给出了相应的解决方法。同时，本文还讨论了在不同文档重排序下对动态索引剪枝算法的影响。实验表明在打分公式中文档静态分数比例较小时，按URL序重排序的索引查询处理的速度比较快。当文档静态分数的比重增加时，则按文档静态分数序排序的索引的查询处理更有优势。4.本文提出一种在区间最大索引中最优化区间划分的方法，并在这种区间划分的方式下，提出了4种动态索引剪枝算法：Space-Max WAND (SMW)，Space-Max MaxScore (SMM)，Space-Max AND (SMA)和Space Max AND withCheck (SMAC)。这种最优化区间划分的方法结合了文档分数估算误差和区间自身的处理开销等因素。它能在同等条件下对索引中的每个倒排链划分出最优的区间。利用区间最大的分数，新提出剪枝算法能更加精确的估算出候选文档的分数，减少找到候选文档的数量，同时对候选文档打分也能更早的结束。实验表明，这种基于最优化区间的方法的剪枝算法比根据倒排链长度来划分区间的方法处理查询的效率高。而基于区间最大索引的剪枝算法比基于块最大索引的剪枝算法效率高。5.在上述的研究成果的基础上，重新设计并实现了天网搜索引擎。使得天网搜索引擎在索引量和查询处理的效率都有非常大的提升。

全文目录

摘要  3-5
Abstract  5-14
第1章引言  14-26
  1.1 研究背景  14-20
    1.1.1 索引剪枝的分类  16-17
    1.1.2 静态索引剪枝的相关研究  17-18
    1.1.3 动态索引剪枝的相关研究  18-20
  1.2 研究问题和内容  20-24
  1.3 研究意义  24
  1.4 论文组织结构  24-25
  1.5 小结  25-26
第2章背景知识  26-39
  2.1 搜索引擎相关知识  26-33
    2.1.1 搜索引擎结构  26-27
    2.1.2 索引切分方式  27-28
    2.1.3 倒排索引结构  28-31
    2.1.4 查询处理方式  31-32
    2.1.5 文档排序方式  32-33
  2.2 索引剪枝的评价指标  33-39
    2.2.1 检索效果指标  34-35
    2.2.2 序列相似性指标  35-36
    2.2.3 检索效率指标  36-39
第3章基于网页结构和重要度的静态索引剪枝  39-56
  3.1 研究问题与内容  39-40
  3.2 经典静态索引剪枝算法的比较  40-42
    3.2.1 倒排链为中心的剪枝  40-41
    3.2.2 文档为中心的剪枝  41-42
    3.2.3 当前研究存在的问题  42
  3.3 基于网页结构和重要度的剪枝算法  42-47
    3.3.1 网页的结构信息  43-44
    3.3.2 网页的重要度计算  44-46
    3.3.3 剪枝算法  46-47
  3.4 实验与结果分析  47-55
    3.4.1 实验设置  47-50
    3.4.2 结果分析  50-55
  3.5 小结  55-56
第4章基于块最大索引的动态索引剪枝  56-97
  4.1 研究问题与内容  56-58
  4.2 经典 DAAT 动态索引剪枝算法比较  58-63
    4.2.1 MaxScore 剪枝算法  58-60
    4.2.2 WAND 剪枝算法  60-63
  4.3 基于块最大索引的动态索引剪枝算法  63-85
    4.3.1 块最大索引结构  63-64
    4.3.2 基于块最大索引的剪枝算法  64-74
    4.3.3 实验与结果分析  74-85
  4.4 包含静态分数的剪枝算法  85-95
    4.4.1 相关性分数与静态分数的结合策略  85-88
    4.4.2 包含静态分数的剪枝算法  88-91
    4.4.3 实验与结果分析  91-95
  4.5 小结  95-97
第5章基于区间最大索引的动态索引剪枝  97-113
  5.1 研究问题与内容  97-98
  5.2 区间最大索引结构  98-99
  5.3 基于区间最大索引的剪枝算法  99-106
    5.3.1 最优化区间划分  99-103
    5.3.2 存储空间优化  103-104
    5.3.3 区间最大索引的剪枝算法  104-105
    5.3.4 区间信息摘要  105-106
  5.4 实验与结果分析  106-112
    5.4.1 实验设置  106-107
    5.4.2 结果分析  107-112
  5.5 小结  112-113
第6章索引剪枝在天网搜索引擎的应用  113-121
  6.1 天网搜索引擎介绍  113-118
    6.1.1 系统结构  113-114
    6.1.2 网页索引  114-116
    6.1.3 网页检索  116-118
  6.2 天网搜索中的索引剪枝  118-120
    6.2.1 天网中的静态索引剪枝  118-119
    6.2.2 天网中的动态索引剪枝  119-120
  6.3 小结  120-121
第7章总结与展望  121-124
  7.1 本文的工作及创新性  121-122
  7.2 未来工作的展望  122-124
参考文献  124-134
博士期间发表论文  134-136
博士期间项目实践和奖励  136-138
致谢  138-139

搜索引擎中索引剪枝的研究

内容摘要

全文目录

相似论文