信息检索中top-k问题的并行算法及优化研究

论文摘要

随着互联网络的发展,以文本形式存储在网络上的信息呈现爆炸式增长。大量积累的动态信息阻碍了人类对它的有效利用。作为大规模文本集合上信息检索工具的搜索引擎在诞生之初就成为解决网络信息访问的重要工具,并在其后的发展中占据着人类信息生活越来越重要的位置。针对某一查询,搜索引擎可能命中数以亿记的查询结果,而用户关心的往往只是符合其查询要求的最优的数十个结果。如何从搜索引擎命中的大量结果中,快速、准确地找出最符合查询需求的结果集合,构成搜索引擎设计的一个关键问题——top-k查询问题。Top-k查询针对分散在不同信息源中的对象,根据聚合函数找出其中分数最优的k个对象。其在信息检索领域具有广泛的应用,并且是影响搜索引擎性能的关键组件。为了提升top-k查询的数据处理能力,加速top-k查询的计算过程,本文以分布式存储系统和共享式存储系统为目标平台,研究top-k查询并行算法设计和性能优化的关键技术。主要的研究工作分为三个部分:一是研究分布式存储平台上的top-k查询并行算法,以解决海量数据的查询问题;二是研究基于任务并行的top-k查询处理,优化查询算法的数据访问开销;三是研究多核处理器平台上top-k查询的计算性能优化,以提高查询的速度满足用户的实时性要求。本文对于并行查询算法和性能优化技术的研究,可以充分利用现有并行计算机的处理能力,解决top-k查询中海量数据处理和实时性相关问题,具有重要的学术价值和应用价值。本文的主要研究成果,贡献和创新点可以概括为以下几点:1.提出处理海量数据的top-k查询并行算法由于top-k查询处理的数据规模日益扩大,单计算机的存储系统难以满足应用需求。本文提出一种数据划分方法,将大规模数据划分到分布式并行机的存储系统上,并针对这种数据划分设计了基于消息传递的top-k查询并行算法,而后通过缩短通信消息长度、减少通信次数等手段进一步优化了该并行算法。2.提出减小数据访问开销的top-k查询并行算法Top-k查询是一种I/O密集型计算问题,数据访问的开销占了总开销的很大比重。本文研究了常用top-k查询算法对数据源的访问方式,提出一种多策略的并行算法减小查询的数据访问开销。通过算法分析,得出了并行算法数据访问开销优于原有算法的必要数值条件,并且给出了并行算法访问开销的一个上界。3.优化多核平台上top-k查询的计算性能随着研究的深入,top-k查询算法被设计得越来越复杂,大部分算法都通过引入额外计算来加快算法终止从而减少数据访问上的开销。在实际的查询程序中,计算部分的时间开销在总开销中所占的比重越来越大。本文在多核处理器平台上研究了禁止随机访问No Random Access（NRA）程序的性能优化问题。通过调整数据结构和使用OpenMP多线程并行,有效的优化了程序的数据级并行和线程级并行,加快了查询程序在多核处理器平台上的运行速度。

论文目录

• 摘要
• ABSTRACT
• 表格
• 插图
• 第1章 绪论
• 1.1 信息检索介绍
• 1.1.1 信息检索基本概念
• 1.1.2 搜索引擎
• 1.1.3 Top-k 查询的定义
• 1.2 并行计算简介
• 1.2.1 并行计算的基本概念
• 1.2.2 并行计算机
• 1.2.3 并行算法
• 1.2.4 并行编程模型
• 1.3 论文研究思路, 内容和成果
• 1.4 论文组织结构
• 1.5 本章小结
• 第2章 基本概念与相关工作综述
• 2.1 Top-k 查询的基本概念
• 2.1.1 Top-k 问题的由来
• 2.1.2 查询的数学模型
• 2.1.3 查询技术的分类
• 2.1.4 算法代价评价
• 2.2 研究现状
• 2.2.1 允许随机访问算法的研究
• 2.2.2 禁止随机访问算法的研究
• 2.2.3 限制随机访问模型的研究
• 2.3 本章小结
• 第3章 分布式存储平台上top-k 查询并行算法
• 3.1 研究背景
• 3.1.1 多媒体数据库
• 3.1.2 机群系统简介
• 3.1.3 MPI 消息传递接口
• 3.2 并行Top-k 查询算法
• 3.2.1 TA 算法介绍
• 3.2.2 数据划分
• 3.2.3 并行TA 算法
• 3.2.4 周期式并行TA 算法
• 3.2.5 实验验证与分析
• 3.3 消息传递的top-k 算法代价分析
• 3.3.1 实验验证与分析
• 3.4 本章小结
• 第4章 Top-k 查询算法的数据访问优化
• 4.1 引言
• 4.2 NRA 算法数据访问优化
• 4.2.1 NRA 算法介绍
• 4.2.2 PNRA 算法
• 4.2.3 PNRA 算法数据访问分析
• 4.2.4 随机化PNRA 算法
• 4.2.5 实验数据与分析
• 4.3 TA 算法的数据访问优化
• 4.3.1 数据访问分析
• 4.3.2 并行选择阈值算法
• 4.3.3 实验验证与分析
• 4.4 本章小结
• 第5章 层次存储结构上top-k 查询优化问题
• 5.1 引言
• 5.1.1 存储器层次结构
• 5.1.2 层次存储结构上top-k 问题代价公式
• 5.2 考虑存储结构的访问优化
• 5.2.1 改进的代价公式
• 5.2.2 分层的NRA 算法
• 5.3 实验数据与性能分析
• 5.3.1 实验配置
• 5.3.2 数据与分析
• 5.4 本章小结
• 第6章 多核平台上top-k 查询的计算性能优化
• 6.1 研究背景
• 6.1.1 Top-k 算法的计算性能
• 6.1.2 多核处理器技术介绍
• 6.1.3 OpenMP 编程模型
• 6.2 NRA 程序计算优化
• 6.2.1 NRA 程序设计
• 6.2.2 串行优化
• 6.2.3 并行优化
• 6.3 实验与分析
• 6.3.1 实验配置
• 6.3.2 串行性能分析
• 6.3.3 可扩展性分析
• 6.4 本章小结
• 第7章 总结和展望
• 7.1 本文总结
• 7.2 进一步工作
• 参考文献
• 致谢
• 在读期间发表的学术论文与取得的研究成果