文档介绍：中国科学技术大学
博士学位论文
信息检索中top-k问题的并行算法及优化研究
姓名:吴超
申请学位级别:博士
专业:计算机软件与理论
指导教师:陈国良
2011-05-05
摘要
摘要
随着互联网络的发展,以文本形式存储在网络上的信息呈现爆炸式增长。
大量积累的动态信息阻碍了人类对它的有效利用。作为大规模文本集合上信息
检索工具的搜索引擎在诞生之初就成为解决网络信息访问的重要工具,并在其
后的发展中占据着人类信息生活越来越重要的位置。针对某一查询,搜索引擎
可能命中数以亿记的查询结果,而用户关心的往往只是符合其查询要求的最优
的数十个结果。如何从搜索引擎命中的大量结果中,快速、准确地找出最符合
查询需求的结果集合,构成搜索引擎设计的一个关键问题——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 查询算法
被设计得越来越复杂,大部分算法都通过引入额外计算来加快算法终止从
I
摘要
而减少数据访问上的开销。在实际的查询程序中,计算部分的时间开销在
总开销中所占的比重越来越大。本文在多核处理器平台上研究了禁止随机
访问 No Random Access(NRA) 程序的性能优化问题。通过调整数据结构和
使用 OpenMP 多线程并行,有效的优化了程序的数据级并行和线程级并
行,加快了查询程序在多核处理器平台上的运行速度。
关键词: Top-k 查询并行计算分布式存储系统共享存储系统
多核处理器性能优化
II
ABSTRACT
ABSTRACT
Along with the rapid development of World Wide Web, billions of documents that
compose the largest human repository of knowledge in history have been created on the
web. However it es more and more difficult for people to find useful information
on web, because of the large number of documents accumulated. Thus search engine,
which helps people tackle the large amount of information on the web, has e more
and more important in information retrieval. When a user poses a quer