《搜索引擎的数据压缩与查询优化》深入浅出地介绍了搜索引擎中倒排索引结构的发展简史以及常用的结构设计和压缩算法、查询算法,并基于作者的研究成果,介绍了几种索引压缩和查询的完整解决方案。
《搜索引擎的数据压缩与查询优化》主要面向信息检索专业方向的研究生、从事搜索引擎相关工作和其他对搜索技术感兴趣的人群。读者除了可从书中获取严谨的理论知识,还可以依照其中的方法重现试验,用于搭建测试平台或者实际使用。
《搜索引擎的数据压缩与查询优化》旨在抛砖引玉,以期为应对信息检索面临的挑战提供参考,限于编者水平,书中不妥之处在所难免,敬请读者批评指正。
随着互联网的发展,各类信息的体量规模增长越来越快。日益增大的数据体量和用户数量给各类信息系统,尤其是搜索引擎带来了严峻的考验。应对这类挑战的关键措施是提升系统在数据爬取收集、整理压缩以及查询应答方面的效率,而倒排索引作为信息检索底层最常用的数据结构,负责对信息进行组织管理和查询处理,对检索效率和系统运营成本有着至关重要的影响。因此,针对倒排索引的压缩和查询优化已经成为信息检索领域一个重要的研究课题。
面对PB级的网页索引数据、成千上万的查询请求和丰富多彩的应用需求,以Google、Bing、百度等为代表的各大商业搜索引擎在不断探索着性能提升的方向,学术界也一直将信息检索中的效率问题作为重点研究对象,在算法设计、硬件特性、数据对象各个方面的优化研究不断推陈出新,诸如SIGIR、VLDB、WWW、CIKM和WSDM等顸会每年都设置专门的主题进行讨论。
本书深入浅出地介绍了搜索引擎中倒排索引结构的发展简史以及常用的结构设计和压缩算法、查询算法,并基于作者的研究成果,介绍了几种索引压缩和查询的完整解决方案。本书主要面向信息检索专业方向的研究生、从事搜索引擎相关工作和其他对搜索技术感兴趣的人群。读者除了可从书中获取严谨的理论知识,还可以依照其中的方法重现试验,用于搭建测试平台或者实际使用。本书旨在抛砖引玉,以期为应对信息检索面临的挑战提供参考,限于编者水平,书中不妥之处在所难免,敬请读者批评指正。
宋省身,1990年出生于河南濮阳,博士毕业于国防科技大学计算机学院,现任国防科技大学前沿交叉学科学院副教授,研究方向为数据分析、信息检索与自然语言处理,承担和参与多项信息检索相关科研课题研究,以首作者发表论文十余篇、申请专利多项。
第1章 搜索引擎中的效率问题
1.1 引言
1.2 背景和意义
1.3 主要研究内容
1.4 组织结构
第2章 信息检索与搜索引擎
2.1 信息检索
2.2 搜索引擎
2.3 倒排索引与检索模型
第3章 倒排索引压缩与查询相关背景知识
3.1 现代硬件体系结构
3.2 倒排索引结构
3.3 倒排索引的压缩算法
3.3.1 面向整数的压缩算法
3.3.2 面向分块的压缩算法
3.3.3 基于SIMD的压缩算法
3.4 倒排链表的求交算法
3.4.1 多倒排链求交算法
3.4.2 搜索算法
3.5 倒排链表的排序查询
3.5.1 相关性模型
3.5.2 两种基本的查询处理方式
3.5.3 top-k查询处理算法研究现状
3.6 本章小结
第4章 基于空间最优划分的倒排索引压缩算法
4.1 引言
4.2 基于近似划分的分块压缩算法
4.2.1 基于DAG的倒排链表划分策略
4.2.2 ExtendedAFOR压缩算法
4.2.3 最优划分的VSEncoding压缩算法
4.3 自启发式划分的Elias-Fano索引压缩算法
4.3.1 分块Elias-Fano索引
4.3.2 线性划分策略
4.4 实验测试与结果分析
4.4.1 基于近似划分的分块压缩算法测试
……
第5章 混合索引在双权重标准下的时空均衡压缩算法
第6章 基于并行指令集的倒排链快速求交算法
第7章 排序查询算法的剪枝加速优化技术
第8章 总结与展望
参考文献