搜索引擎中索引技术研究与实现

论文摘要

本文主要围绕搜索引擎中核心技术之一的倒排索引技术进行展开,主要包括索引的组织结构,构建过程,压缩编码技术,动态更新技术,大规模数据存储技术等,其中以索引压缩、动态更新和大规模数据存储为研究重点,并在此基础上设计了一个用于实验环境的原型系统。索引压缩和编码可以有效节约存储空间,减少I/O流量,提高系统吞吐率。压缩的缺点是在对索引进行处理时需要解压缩,比如查询、更新,会占用一定的CPU时间。本文提出了一种混合编码策略,其有效地在压缩率、解压时间和动态性能之间达到权衡。索引动态更新是为了支持在现实检索环境下文本集频繁地进行变化的动态检索环境。本文对比了几种动态更新策略,对它们在索引构建和动态维护中通过实验进行了对比分析。在此基础上,针对实时性要求较高动态检索环境,对在线索引技术进行了探讨。在线索引是当前研究的热点和难点,其允许在动态更新的同时提供检索服务,以满足高实时性的要求。针对大规模数据的存储和处理问题,设计了一种分布式数据存储和处理策略,其既有效的满足了数据的分布式存储和数据处理的要求,又具有很高的容错性。

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 研究背景
• 1.2 全文索引关键技术
• 1.2.1 索引的压缩和编码
• 1.2.2 索引的动态更新
• 1.2.3 大规模数据的存储和处理
• 1.3 课题研究主要内容
• 1.4 本文组织结构
• 第二章 搜索引擎中索引组织
• 2.1 全文索引技术
• 2.1.1 全文索引概述
• 2.1.2 全文索引模型
• 2.2 倒排索引技术
• 2.2.1 正向索引
• 2.2.2 倒排索引
• 2.2.3 索引的构建流程
• 2.2.4 倒排表的组织
• 2.3 Google 索引技术
• 2.3.1 Google 索引的数据结构
• 2.3.2 Google 索引过程
• 2.3.3 Google 索引模块
• 2.4 本章小结
• 第三章 倒排索引压缩
• 3.1 概述
• 3.2 倒排索引压缩相关技术
• 3.3 正整数变长编码
• 3.3.1 字节对齐编码
• 3.3.2 位对齐编码
• 3.3.3 各种编码性能评价
• 3.4 混合编码策略
• 3.4.1 混合编码基本思想
• 3.4.2 实验及性能分析
• 3.5 本章小结
• 第四章 倒排索引动态维护
• 4.1 概述
• 4.2 索引构建技术
• 4.2.1 离线索引构建
• 4.2.2 在线索引构建
• 4.3 索引的动态维护策略
• 4.3.1 In-Place 索引维护
• 4.3.2 Merge-based 索引维护
• 4.3.3 混合索引维护
• 4.3.4 基于阈值的垃圾收集
• 4.4 在线索引维护
• 4.4.1 几何分块在线索引维护
• 4.4.2 动态平衡树在线索引维护
• 4.5 实验及性能分析
• 4.6 本章小结
• 第五章 系统设计与实现
• 5.1 系统总体设计
• 5.1.1 系统整体架构
• 5.1.2 系统数据流程
• 5.2 系统的详细设计
• 5.2.1 主要模块设计
• 5.2.2 索引结构设计
• 5.2.3 索引文件设计
• 5.2.4 系统性能测试
• 5.3 分布式和扩展性考虑
• 5.3.1 基于Map-Reduce 的分布索引
• 5.3.2 分布式存储系统
• 5.3.3 容错性能测试
• 5.4 本章小结
• 第六章 总结与展望
• 6.1 本文总结
• 6.2 本论文存在的不足
• 6.3 下一步的工作
• 致谢
• 参考文献
• 研究成果